Bảng băm (HashTable)- chương trình từ điển

Viết chương trình Từ điển sử dụng cấu trúc bảng băm với các chức năng sau
• Thêm một từ mới
• Tra từ
• Cập nhật từ (sửa đổi nội dung)
• Xoá từ

CHƯƠNG TRÌNH MINH HỌA BẢNG BĂM DÙNG PHƯƠNG PHÁP DÒ TUYẾN TÍNH, GIÁ TRỊ LƯU TRỮ LÀ SỐ NGUYÊN

C Code:

Select All | Show/Hide

1. #include<stdio.h>
2. #include<conio.h>
3. #define M 11  // khai bao kich thuoc bang bam
4. #define NULLKEY -365  // khai bao nut rong co gia tri la -365
5. #define TRUE 1
6. #define FALSE 0
7. int BangBam[M];  // tao bang bam voi kich thuoc M
8. int SoNut; // so nut cua bang bam
9. int HamBam(int k)
10. {
11.     return k%M;
12. }
13. void KhoiTaoBangBam()
14. {
15.     for(int i=0;i<M;i++)
16.         BangBam[i]=NULLKEY;
17. }
18. int Full()  // kiem tra xem bang bam da day hay chua?
19. {
20.     if (SoNut==M-1) return TRUE;
21.     else return FALSE;
22. }
23. int Search(int k)  // tim kiem khoa K co o trong bang bam hay khong?
24. {
25.     int i=HamBam(k);
26.     while (BangBam[i]!=k && BangBam[i]!=NULLKEY)
27.     {
28.         i++;
29.         if (i>=M) i=i-M;
30.     }
31.     if (BangBam[i]==k) return i;
32.     else return M;
33. }
34. int ThemPhanTu(int k) // them khoa k vao bang bam
35. {
36.     int i,j;
37.     if (Full())
38.     {
39.         printf("\nBang bam da day");
40.         return 0;
41.     }
42.     i=HamBam(k);
43.     while (BangBam[i]!=NULLKEY)
44.     {
45.         i++;
46.         if (i>=M) i=i-M;
47.     }
48.     BangBam[i]=k;
49.     SoNut++;
50.     return i;
51. }
52. void InBangBam()  
53. {
54.     printf("\nBANG BAM CUA BAN:\n");
55.     printf("\n\t\tVi tri\t\t\tKhoa\n");
56.     for(int i=0;i<M;i++)
57.         if (BangBam[i]!=NULLKEY)
58.             printf("\n\t\t%d\t\t\t%d",i,BangBam[i]);
59.         else
60.             printf("\n\t\t%d\t\t\tNULL",i);
61. }
63. void main()
64. {
65.     clrscr();
66.     int khoa_nhap,khoa_tim;
67.     KhoiTaoBangBam();
68.     printf("\tCHUONG TRINH MINH HOA BANG BAM DUNG PHUONG PHAP TIM TUYEN TINH");
69.     for(int i=0;i<M-1;i++)
70.     {
71.         printf("\nNhap phan tu thu %d:",i+1);
72.         scanf("%d",&khoa_nhap);
73.         ThemPhanTu(khoa_nhap);
74.     }
75.     InBangBam();
76.     printf("\n\nNhap vao khoa ban can tim:");
77.     scanf("%d",&khoa_tim);
78.     int result=Search(khoa_tim);
79.     if (result==M) printf("Khong tim thay %d trong bang bam",khoa_tim);
80.     else printf("\nTim thay roi! %d nam o vi tri thu %d trong bang bam",khoa_tim,result);
81.     getch();
82. }

Source code[Đồ án-C#]: 

Liên hệ: vuthanhnam94@gmail.com

Quản lý bán Cafe

Phân tích đề tài: Quản lý bán Cafe

B: XÂY DỰNG CHƯƠNG TRÌNH

B.1. MÔ TẢ BÀI TOÁN NGHIỆP VỤ

B.1.1. Khảo sát hiện trạng

      a. Giới thiệu chung vấn đề

      Khi có khách bước vào nhân viên phục vụ sẽ mở cửa cho khách. Hỏi khách muốn dùng tại quán hay mang về (cách thức thanh toán) cùng với số lượng người đi (nếu dùng tại quán) để có thể sắp xếp chỗ ngồi một cách hợp lý nhất. Sau khi chọn chỗ ngồi cho khách viên phục vụ sẽ đưa Menu cho khách để khách chọn đồ uống… Sau khi đã nhập hết các order của khách, nhân viên phục vụ thanh toán với khách hàng và in hóa đơn (2 hóa đơn). Một hóa đơn sẽ chuyển cho nhân viên pha chế, một hóa đơn giao cho khách hàng. Khi pha chế xong các đồ uống nhân viên phục vụ sẽ mang ra cho khách. Ngoài ra nhân viên muốn có các nguyên liệu để pha chế còn phải lấy lên từ kho bảo quản.

Từ những lý do trên đề  tài quản lý quán café sẽ được chia làm 4 phần nhỏ : quản lý bán hàng, quản lý nhân viên, quản lý kho, quản lý lương.

            b. Mô tả nghiệp bài toán nghiệp vụ

Một quán café luôn bao gồm 1 cửa ra vào, bên trong cửa hàng luôn được bố trí, sắp xếp thành từng dãy bàn nối tiếp nhau theo các phong cách riêng.

·         Quản lý nhân viên:

o    Quản lý nhân viên được chia thành 4 phần nhỏ: Quản lý ca, Quản lý thông tin nhân viên, Quản lý hệ số lương. Qua quản lý ca ta có thể nắm rõ số nhân viên tham gia và thời gian bắt đầu đến kết thúc ca, và lương cho từng ca. Quản lý thông tin nhân viên giúp chúng ta có thể biết số lượng nhân viên trong quán cũng như thời gian họ công tác tại đây, và lý lịch cá nhân của họ. Và một phần rất quan trọng nữa là quản lý tăng ca: cho biết những nhân viên nào tham gia làm ca nào và họ có thể đăng ký nhiều ca trong một ngày.

·         Quản lý nhân viên:

o    Quản lý lương sẽ chấm công và tính lương cho mỗi nhân viên làm việc theo ca trong một ngày nhân với hệ số lương, cuối tháng Hệ Thống xẽ đưa ra bảng danh sách châm công nhân viên trong tháng đó và tính lương cả tháng cho mỗi nhân viên dựa vào số công mà mỗi nhân viên làm việc trong tháng.

·         Quản lý bán hàng:

o    Quản lý bán hàng sẽ làm các việc như quản lý các sản phẩm, nhận các yêu cầu và phản hồi từ khách hàng, lập các hóa đơn….

·         Quản lý kho :

o    Khi nhận được yêu cầu nhập hàng từ phòng thông tin gửi đến, người quản lý kho có trách nhiệm làm thủ tục nhập hàng theo hóa đơn, viết phiếu nhập kho .Kiểm tra và xác nhận các mặt hàng vừa nhập.Đưa số hàng vừa nhập vào kho 

o    Mỗi mặt hàng nhập về có thể được lưu trữ ở các kho khác nhau, một kho  có thể lưu trư được nhiều mặt hàng khác nhau.

o    Khi phiếu yêu cầu xuất kho được gửi đến ,người quản lý kho kiểm tra lại số lượng sản phẩm cần xuất trong các kho và lập phiếu xuất kho, xuất các mặt hàng theo yêu cầu.

o    Nếu số lượng sản phẩm hiện có trong kho không đủ so với số lượng cần xuất. Người quản lý kho có thể ngừng chưa xuất sản phẩm và đề nghị nhập sản phẩm sau đó mới xuất đủ 1 lần theo yêu cầu.

o    Một nhà cung cấp có thể cung cấp nhiều mặt hàng  và 1 cửa hàng có thể nhập hàng từ nhiều nhà cung cấp khác nhau.

o    Hàng ngày người quản lý có trách nhiệm tổng kết các mặt hàng xuất nhập trong ngày.

o    Cuối tháng người quản lý kho tổng hợp các phiếu nhập kho-xuất kho hợp lệ để ghi lại vào sổ.Sau đó kiểm kê số lượng sản phẩm nhập xuất, số lượng hàng tồn, hàng hỏng.

      Chương trình : https://www.youtube.com/watch?v=jh90pE9Y-  FU&list=UUjYqfQNmLRUVQyG-iGbmT0g                                                                                                                  

Source code[FULL]: 

Liên hệ: vuthanhnam94@gmail.com

[Thuật toán] Thuật toán minmax (cắt tỉa anpha-beta)

Xét một trò chơi trong đó hai người thay phiên nhau đi nước của mình như cờ vua, cờ tướng, carô,… Trò chơi có một trạng thái bắt đầu và mỗi nước đi sẽ biến đổi trạng thái hiện hành thành một trạng thái mới. Trò chơi sẽ kết thúc theo một quy định nào đó, theo đó thì cuộc chơi sẽ dẫn đến một trạng thái phản ánh có một người thắng cuộc hoặc một trạng thái mà cả hai đấu thủ không thể phát triển được nước đi của mình, ta gọi nó là trạng thái hòa cờ. Ta tìm cách phân tích xem từ một trạng thái nào đó sẽ dẫn đến đấu thủ nào sẽ thắng với điều kiện cả hai đấu thủ đều có trình độ như nhau.

Một trò chơi như vậy có thể được biểu diễn bởi một cây, gọi là cây trò chơi. Mỗi một nút của cây biểu diễn cho một trạng thái. Nút gốc biểu diễn cho trạng thái bắt đầu của cuộc chơi. Mỗi nút lá biểu diễn cho một trạng thái kết thúc của trò chơi (trạng thái thắng thua hoặc hòa). Nếu trạng thái x được biểu diễn bởi nút n thì các con của n biểu diễn cho tất cả các trạng thái kết quả của các nước đi có thể xuất phát từ trạng thái x.

Ví dụ 3-5: Xét trò chơi carô có 9 ô. Hai người thay phiên nhau đi X hoặc O. Người nào đi được 3 ô thẳng hàng (ngang, dọc, xiên) thì thắng cuộc. Nếu đã hết ô đi mà chưa phân thắng bại thì hai đấu thủ hòa nhau. Một phần của trò chơi này được biểu diễn bởi cây sau:

Trong cây trò chơi trên, các nút lá được tô nền và viền khung đôi để dễ phân biệt với các nút khác. Ta có thể gán cho mỗi nút lá một giá trị để phản ánh trạng thái thắng thua hay hòa của các đấu thủ. Chẳng hạn ta gán cho nút lá các giá trị như sau:

· 1 nếu tại đó người đi X đã thắng,

· -1 nếu tại đó người đi X đã thua và

· 0 nếu hai đấu thủ đã hòa nhau.

Như vậy từ một trạng thái bất kỳ, đến lượt mình, người đi X sẽ chọn cho mình một nước đi sao cho dẫn đến trạng thái có giá trị lớn nhất (trong trường hợp này là 1). Ta nói X chọn nước đi MAX, nút mà từ đó X chọn nước đi của mình được gọi là nút MAX. Người đi O đến lượt mình sẽ chọn một nước đi sao cho dẫn đến trạng thái có giá trị nhỏ nhất (trong trường hợp này là -1, khi đó X sẽ thua và do đó O sẽ thắng). Ta nói O chọn nước đi MIN, nút mà từ đó O chọn nước đi của mình được gọi là nút MIN. Do hai đấu thủ luân phiên nhau đi nước của mình nên các mức trên cây trò chơi cũng luânphiên nhau là MAX và MIN. Cây trò chơi vì thế còn có tên là cây MIN-MAX. Ta có thể đưa ra một quy tắc định trị cho các nút trên cây để phản ánh tình trạng thắng thua hay hòa và khả năng thắng cuộc của hai đấu thủ.

Nếu một nút là nút lá thì trị của nó là giá trị đã được gán cho nút đó. Ngược lại, nếu nút là nút MAX thì trị của nó bằng giá trị lớn nhất của tất cả các trị của các con của nó. Nếu nút là nút MIN thì trị của nó là giá trị nhỏ nhất của tất cả các trị của các con của nó.

Quy tắc định trị này cũng gần giống với quy tắc định trị cho cây biểu thức số học, điểm khác biệt ở đây là các toán tử là các hàm lấy max hoặc min và mỗi nút có thể có nhiều con. Do vậy ta có thể dùng kỹ thuật quay lui để định trị cho các nút của cây trò chơi.

Để cài đặt ta có một số giả thiết sau:

· Ta có trường info cho ta giá trị của.
· Các hằng 2 và -2 tương ứng là các trị lớn nhất và nhỏ nhất của từng nút.
· Một biến c kiểu char để xác định định trị cho nút là X hay O đi.
· Một kiểu pointer được khai báo một cách thích hợp để biểu diễn cho một nút trên cây phản ánh một trạng thái của cuộc chơi.
· Ta có một hàm nutLa() để xác định xem một nút có phải là nút lá hay không?
· Hàm max và min tương ứng lấy giá trị lớn nhất và giá trị nhỏ nhất của hai giá trị.

Giải thuật vét cạn định trị cây trò chơi
Hàm val nhận vào một nút q và ký tự c trả về giá trị của nút.

Nếu nút q là nút lá thì trả về giá trị đã được gán cho nút lá. Ngược lại ta cho q một giá trị tạm value là -2 hoặc 2 tùy thuộc q là nút X hay O và xét con của q. Sau khi một con của q có giá trị V thì đặt lại val = max(val,V) nếu q là nút X và value = min(val,V) nếu q là nút O. Khi tất cả các con của q đã được xét thì giá trị tạm val của q trở thành giá trị của nó.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

{Ham tra ve gia tri trang thai khi dung minmax - thuat toan minmax} function val(var q: pointer; c: char; Vp: item): item; var     i: integer; begin     if (nutLa(q)) then      {Neu la nut la thi lay ngay KQ gia tri cua nut do}         begin                 {writeln(q^.lab,'->>> ', q^.info);}                 val:= q^.info;         end     else     begin         for i:= 1 to q^.numChild do   {Duyet cac nut con cua q}         begin             if c = 'X' then       {Neu dang la luot X}             begin                 q^.info:= max(q^.info, val(q^.child[i], 'O', q^.info));                 {writeln(q^.lab,'->>> ', q^.info);}                 val := q^.info;             end             else                    {Nguoc lai la luot O}             begin                 q^.info:= min(q^.info, val(q^.child[i], 'X', q^.info));                 {writeln(q^.lab,'->>> ', q^.info);}                 val := q^.info;                 break;             end;         end;     end; end;

Áp dụng vào cây tổng quát T ta có cài đặt:

1 2 3 4 5 6 7 8 9 10

procedure catTia(var T: pointer);  {Dua thuat toan vao cay} var     p: pointer;     i: integer; begin     if T <> nil then     begin         T^.info := val (T, 'X', T^.info);     end; end;

Chuơng trình hoàn chỉnh các bạn có thể xem tại đây