Sáng tạo trong thuật toán và lập trình - Tập 4
Trang chủ   |   Đăng nhập  |  Đăng ký  |  
 
Khoa
Login
Tên truy nhập:
Mật khẩu:
Quên mật khẩu ?
Giỏ hàng 0 SP   |  Sơ đồ site
phone1.png 024.3577.2138 (Giờ hành chính)
phone2.png 0916.18.16.54
phone2.png 0904.251.013 
phone1.png 024. 3577.2145
  
Sách
Sáng tạo trong thuật toán và lập trình - Tập 4
Sáng tạo trong thuật toán và lập trình - Tập 4
Mã sách: 9786048029617
Tác giả: PGS.TS Nguyễn Xuân Huy
Nhà xuất bản: Thông tin và Truyền thông
Loại sách:
  - Sách in
Giá Bán: 85.000 VNĐ
Giá bìa: 85.000 VNĐ
Số lượng :
giohang
Hướng dẫn thanh toán
Số trang: 319
Kích thước: 14.5x20.5
Trọng lượng: 300 gram
Hình thức bìa: Bìa mềm
Năm xuất bản: 2018
Số lượng trong kho: 196
Số lần xem: 567

Với mục đích cung cấp những kiến thức cơ bản về lập trình trong Pascal và C++ cho các bạn học sinh, sinh viên và những bạn đọc muốn tự hoàn thiện tri thức trong lĩnh vực giải thuật và lập trình; Nhà xuất bản Thông tin và Truyền thông xuất bản cuốn sách “Sáng tạo trong thuật toán và lập trình” (tập 4) do PGS.TSKH. Nguyễn Xuân Huy biên soạn. Cuốn sách này là tập tiếp theo của các tập trước đã xuất bản

MỤC LỤC

Lời nói đầu

Chương 1. Kỹ thuật Find-Union    

1.1 Công viên  7

1.2 Thành phần liên thông

1.3 Tính liên thông

1.4 Chu trình  

1.5 Cây khung

1.6 Cây khung cực tiểu

1.7 Rừng khung     

1.8 Rừng khung cực tiểu    

1.9 Mạng   

1.10 Van nước

1.11 Cầu    

1.12 Giao khung    

1.13 Đỉnh khớp     

1.14 Liên thông hóa    

1. 15 Chia đội 

1.16 Kiến   

Chương 2. Các bài toán nội dung số   

2.1 Sàng Eratosthenes 

2.2 Biểu diễn số     

2.3 Bậc của thừa số    

2.4 Phân tích ra thừa số nguyên tố

2.5 Bậc của thừa số nguyên tố trong giai thừa

2.6 Các số 0 tận cùng

2.7 Bậc của thừa số pk trong giai thừa

2.8 Bậc của thừa số u trong giai thừa  

2.9 Tổng kết về bậc    

2.10 Tổng ước

2.11 Tổng kết về ước  

Chương 3. Các bài toán nâng cao  

3.1 Lũy thừa 2, 3, 5    

3.2 Số hoàn thiện   

3.3 Phân tích số lớn    

3.4 Bậc cao

3.5 Lũy thừa   

3.6 Ba lô    

3.7 Ba lô đơn giản

3.8 Hình vuông và tam Giác   

3.9 Chiều dài của giai thừa

3.10 Số ước chẵn lẻ    

3.11 Operators (Toán tử)   

3.12 Người thắng cử   

3.13 Cặp điểm gần nhất     

3.14 Mọi đường ngắn nhất

3.15 Đường đi và chu trình Euler   




Thuật toán Hierholzer

Năm 1873, Hierholzer đề xuất một thuật toán tìm chu trình Euler hiệu quả hơn thuật toán Fleury.

  • Bước 1. (Khởi động) Chọn đỉnh s tùy ý làm đỉnh xuất phát.
  • Bước 2. (Tiến) Đi theo các cạnh mới (cạnh chưa thăm) đến mức tối đa. Lần lượt ghi nhận đường đi thể hiện qua các đỉnh đầu mút vào một ngăn xếp p.
  • Bước 3. (Kiểm tra) Nếu mọi cạnh đều đã thăm: thực hiện bước 5 để kết thúc; nếu không: thực hiện bước 4.
  • Bước 4. (Lùi) Dỡ dần ngăn xếp p, tức là bạn quay lui, để tìm một đỉnh đầu tiên w, nơi từ đó có khả năng đi tiếp theo một cạnh chưa thăm. Hãy ghi nhận lại các đỉnh đã dỡ từ ngăn xếp vào một mảng r rồi lặp lại bước 2 để đi tiếp từ đỉnh w này theo các cạnh chưa thăm giống như đã làm với đỉnh v.
  • Bước 5. (Kết) Ghép tiếp mảng r chứa các đỉnh đã dỡ từ ngăn xếp p vào cuối p để nhận được chu trình Euler.  

Chương trình dưới đây thực hiện các thủ tục sau:

Ø  Đọc dữ liệu mô tả đồ thị liên thông G gồm n đỉnh và m cạnh.

Ø  Đếm số đỉnh lẻ k và quyết định:

·    Nếu k > 2: Ghi kết quả 0 với ý nghĩa: G không có đường (và dĩ nhiên là không có chu trình) Euler.

·    Nếu k = 2: Hiển thị một đường Euler.

·    Nếu k = 0: Hiển thị một chu trình Euler.

Chương trình hiển thị kết quả trung gian tại mỗi bước quay lui.

Sơ đồ chính của chương trình sẽ như sau:

Đọc dữ liệu;

int Euler(int s){

    while(1) {

         Tien và ghi nhận các bước tiến vào stack p;

         Nếu Đã duyệt hết cạnh: thoát lặp;    

         Nếu chưa duyệt hết cạnh:

   - Quay lui chuyển các đỉnh lui về cuối p;

          - Nếu không quay lui được: thoát lặp;

    } // end while;

    - Thông báo kết quả;

}

Thủ tục Tiến sẽ xuất phát từ đỉnh s và thêm dần các đỉnh đến vào stack p, từ p[k] đến p[e].

Thủ tục Lui sẽ chạy ngược từ e đến k để tìm một đỉnh i trên đường lùi thoả điều kiện: từ i có cạnh chưa thăm.

Chương trình C++ (Phương án 1)

// Duong va chu trinh Euler. Phuong an 1

#include <iostream>

#include <fstream>

#include <string.h>

#include <stdlib.h>

#include <time.h>

using namespace std;

const int MN = 501;

typedef int mi1[MN];

typedef mi1 mi2[MN];

 

mi2 c; // ma tran ke c[i][j] = c[j][i]

mi1 bac;

mi1 r; // cac dinh chua duyet

int ir; // index for r

mi1 p; // Path

int k; // ngon stack: chi so tien

int last; // chi so lui

int n; // so dinh

int m; // so canh

int dinhLe1, dinhLe2; // 2 dinh le, neu co

 

// Hien thi mang c[d..c] voi thong bao msg

void Print(mi1 a, int d, int c, const char *msg = ""){

cout << msg;

    for (int i = d; i <= c; ++i){

  cout << a[i] << " ";

    }

}

// Hien thi mang 2 chieu a voi thong bao msg

void Print(mi2 a, int d, int c, const char *msg = ""){

    cout << msg;

    for (int i = d; i <= c; ++i)

  Print(a[i],d,c,"\n ");

}

 

void Go(){


PGS. TSKH Nguyễn Xuân Huy sinh năm 1944 tại Thành phố Hải Phòng.

Ông hiện là Chủ tịch Hội đồng Tư vấn Giáo dục Microsoft Việt Nam;

Nghiên cứu viên cao cấp Viện Công nghệ thông tin, Viện Khoa học và Công nghệ Việt Nam.

Họ và tên (*)
Email (*)
Nội dung (*)