intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Sáng kiến kinh nghiệm THPT: Kỹ thuật dùng bit trạng thái để xử lý hiệu quả bài toán Tin học

Chia sẻ: Hương Hoa Cỏ Mới | Ngày: | Loại File: PDF | Số trang:35

Thêm vào BST
Báo xấu
23
lượt xem 2
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Mục tiêu nghiên cứu của sáng kiến là cung cấp kiến thức về việc sử dụng các phép toán logic từ đó giúp cho việc thiết kế các biểu thức logic dùng rất nhiêu trong các phép toán điều kiện được nhanh chóng, chính xác, hiệu quả. Hơn nữa trong đề tài này sẽ phân tích sự hiệu quả của việc chuyển bài toán từ phương pháp xử lý thông thường sang phương pháp xử lý bit.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Sáng kiến kinh nghiệm THPT: Kỹ thuật dùng bit trạng thái để xử lý hiệu quả bài toán Tin học

  1. Kỹ thuật dùng bit trạng thái để xử lý hiệu quả bài toán Tin học Kỹ thuật dùng bit trạng thái để xử lý hiệu quả bài toán Tin học MỤC LỤC A. ĐẶT VẤN ĐỀ .................................................................................................. 3 I. LÝ DO CHỌN ĐỀ TÀI ................................................................................... 3 II. CƠ SỞ LÝ LUẬN .......................................................................................... 4 III. CƠ SỞ THỰC TIỄN ..................................................................................... 4 1. Thuận lợi: ..................................................................................................... 4 2. Khó khăn:..................................................................................................... 4 IV. NỘI DUNG ................................................................................................... 5 V. PHẠM VI ỨNG DỤNG CỦA ĐỀ TÀI .......................................................... 5 B. NỘI DUNG....................................................................................................... 6 I. CÁC KIẾN THỨC CƠ BẢN VỀ BIT TRẠNG THÁI ..................................... 6 1. Phép đảo bit Not ........................................................................................... 6 2. Phép AND .................................................................................................... 7 3. Phép OR ....................................................................................................... 7 4. Phép phủ định NOT ..................................................................................... 8 5. Phép XOR .................................................................................................... 8 6. Phép dịch trái > ........................................................................................ 9 II. CÁC BÀI TOÁN MINH HỌA VỀ XỬ LÝ BIT TRẠNG THÁI .................. 10 Bài toán 1 ....................................................................................................... 10 Bài toán 2 ....................................................................................................... 10 Bài toán 3: ...................................................................................................... 12 Bài toán 4: Phép cộng .................................................................................... 13 Bài toán 5. Tập con ........................................................................................ 13 Bài toán 6: Trò chơi NIM ............................................................................... 14 Bài toán 7. Số khác ........................................................................................ 16 Bài toán 8. Xâu cô lập .................................................................................... 18 Bài toán 9. FIRSTROW ................................................................................ 20 Bài toán 10. Dãy số ....................................................................................... 21 Bài toán 11: Đầu bếp ...................................................................................... 23 Trang 1
  2. Kỹ thuật dùng bit trạng thái để xử lý hiệu quả bài toán Tin học Bài toán 12: Biểu diễn trạng thái. ................................................................... 25 Bài toán 13: Quy hoạch động ......................................................................... 26 Bài toán 14: Chọn ô ....................................................................................... 28 Bài toán 15: Chuyến du lịch - TRIP ............................................................... 32 Bài toán 16: Cô gái chăn bò - COWGIRL ...................................................... 33 C. KẾT LUẬN .................................................................................................... 35 Trang 2
  3. Kỹ thuật dùng bit trạng thái để xử lý hiệu quả bài toán Tin học A. ĐẶT VẤN ĐỀ I. LÝ DO CHỌN ĐỀ TÀI Trong thời đại hiện nay công nghệ thông tin đã thực sự bùng nổ và đã có tác động rất lớn đến với công cuộc phát triển kinh tế - xã hội của con người, của đất nước (và thực tế ta có thể nói rằng ta đang sống trong kỉ nguyên số, kỉ nguyên công nghệ thông tin). Đảng và nhà nước ta đã xác định rõ là để đất nước phát triển thì một trong những yếu tố làm nền tảng là làm sao các ứng dụng của Tin học – công nghệ thông tin phải đưa vào triệt để trong các lĩnh vực của xã hội. Những yêu cầu đẩy mạnh của các ứng dụng công nghệ thông tin, đào tạo nguồn nhân lực đáp ứng yêu cầu Công nghiệp hóa, Hiện đại hóa, mở cửa và hội nhập, hướng đến nền kinh tế tri thức của đất nước ta nói riêng, thế giới nói chung. Chính vì xác định được tầm quan trọng đó, tôi nghĩ đào tạo và cung cấp cho đất nước những nhà lập trình viên giỏi là việc làm hết sức cần thiết. Tin học lập trình là một môn học khó đối với học sinh THPT. Làm thế nào để học sinh hiểu, học tốt, yêu thích và tham gia tốt các kỳ thi học sinh giỏi Tin học là điều mà nhiều giáo viên dạy tin học trăn trở. Là giáo viên dạy tin nhiều năm tôi thấy việc trang bị cho các em học sinh các kiến thức về thuật toán và giải quyết vấn đề một cách khoa học là rất cần thiết, điều đó giúp học sinh hứng thú hơn trong học tập bởi các em tự kiến tạo tri thức hoặc tham gia vào việc kiến tạo tri thức cho mình dựa trên tri thức đã có, bổ sung và làm cho tri thức cũ hoàn chỉnh hơn. Học sinh học tập tự giác, tích cực, vừa kiến tạo tri thức, vừa học đựơc cách giải quyết vấn đề, lại vừa rèn luyện được những đức tính quý báu như tính chủ động, tích cực, tính kiên trì vượt khó, tính kế hoạch và thói quen tự kiểm tra… Trong đề tài này, tôi xin được đề cập tới “Kỹ thuật dùng bit trạng thái để xử lý hiệu quả bài toán tin học”. Như chúng ta đã biết, bộ nhớ của máy tính được lưu trữ dưới dạng mã hóa của hệ nhị phân theo bảng mã IISCI. Bản chất máy tính chỉ hiểu được mã nhị phân dưới dạng dãy số 0 và 1. Mỗi con số như vậy được gọi là một bit. Bít là đơn vị nhỏ nhất để lưu trữ dữ liệu trong máy tính điện tử, mỗi bit chứa số 0 hoặc 1. Chính vì vậy khi lập trình nếu ta chuyển bài toán về xử lý dưới dạng bit thì tốc độ của chương trình được đẩy nhanh rất nhiều. Ngôn ngữ lập trình cung cấp cho chúng ta những toán tử để chúng ta có thể thao tác trên bit như các phép cơ bản and, or, not, xor, dịch trái, dịch phải. Trong Trang 3
  4. Kỹ thuật dùng bit trạng thái để xử lý hiệu quả bài toán Tin học đề tài này tôi sẽ cung cấp kiến thức về việc sử dụng các phép toán logic từ đó giúp cho việc thiết kế các biểu thức logic dùng rất nhiêu trong các phép toán điều kiện được nhanh chóng, chính xác, hiệu quả. Hơn nữa trong đề tài này sẽ phân tích sự hiệu quả của việc chuyển bài toán từ phương pháp xử lý thông thường sang phương pháp xử lý bit. II. CƠ SỞ LÝ LUẬN Qua nhiều năm giảng dạy, bồi dưỡng học sinh giỏi môn Tin học tôi nhận thấy: - Việc trang bị cho các em học sinh các kiến thức về thuật toán và giải quyết vấn đề một cách khoa học là rất cần thiết. - Phương pháp dùng kỹ thuật bit trạng thái để xử lý thực sự hiệu quả bài toán tin học. - Trong tất cả các kỳ thi chọn học sinh giỏi Tỉnh, các bài toán dùng phương pháp bit trạng thái thực sự rất hiệu quả III. CƠ SỞ THỰC TIỄN Một số thuận lợi và khó khăn khi thực hiện chuyên đề sáng kiến kinh nghiệm ở trường. 1. Thuận lợi: - Môn Tin học là một môn học mới nhưng được sự ủng hộ của Cấp trên, Sở giáo dục và Đào tạo, cấp Ủy, nhà trường đã tạo được điều kiện sắm sửa phòng máy và các trang thiết bị cần thiết. - Trường có cơ sở vật chất tốt. - Học sinh rất hứng thú đối với môn học này - Môn học có ứng dụng rất lớn trong thực tiễn nên học sinh rất chịu khó nghiên cứu học tập. - Hàng năm kết quả thi học sinh giỏi môn Tin đạt kết quả cao nên tạo động lực lớn cho học sinh quyết tâm học tập. 2. Khó khăn: - Các tài liệu bồi dưỡng học sinh giỏi môn tin còn rất ít. - Giáo viên đủ chuẩn để bồi dưỡng học sinh giỏi môn tin còn hạn chế. Trang 4
  5. Kỹ thuật dùng bit trạng thái để xử lý hiệu quả bài toán Tin học - Là môn học khó, đòi hỏi người học hội tụ quá nhiều phẩm chất như: Thông minh, tư duy tốt, kiên trì, có năng khiếu về lập trình, cẩn thận, nhanh nhạnh nhưng chính xác tuyệt đối trong từng kỹ thuật nhỏ... IV. NỘI DUNG - Các kiến thức cơ bản về bit trạng thái - Các bài toán minh họa ứng dụng xử lý bit V. PHẠM VI ỨNG DỤNG CỦA ĐỀ TÀI Nội dung của đề tài được sử dụng làm tài liệu cho các học sinh ở các trường THCS, THPT yêu thích môn tin học lập trình. Đề tài cũng là tài liệu cho các đồng nghiệp trong và ngoài Tỉnh yêu thích bộ môn Tin học. Trang 5
  6. Kỹ thuật dùng bit trạng thái để xử lý hiệu quả bài toán Tin học B. NỘI DUNG I. CÁC KIẾN THỨC CƠ BẢN VỀ BIT TRẠNG THÁI Quy ươc về vị trí của các bit: Mỗi byte bao gồm 8 bit được mã số từ phải sang trái còn gọi là bit thấp đến bit cao. Bit nằm ở bên phải được xem là thấp hơn bit nằm ở bên trái. Các bit được đánh số như sau: 7 6 5 4 3 2 1 0. Mỗi bit có thể nhận 1 trong 2 giá trị là 0 hoặc 1. Tại mỗi thời điểm thực hiện chương trình mỗi bit đươc nhận giá trị xác định. Mọi số nguyên trong máy đều biểu diễn dưới dạng nhị phân, ví dụ số 19 được biểu diễn như sau: Bit 7 6 5 4 3 2 1 0. Giá trị 0 0 0 1 0 0 1 1 (số 19). Các phép toán logic trên bit có các phép cơ bản and, or, not, xor, dịch trái, dịch phải. Các phép toán sau đây thực hiện trên các giá trị nguyên và cho kết quả là các giá trị nguyên. 1. Phép đảo bit Not Đổi giá trị của mọi bit từ 0 thành 1 và ngược lại. Trong C phép đảo được kí hiệu là ~ . Ví dụ Các toán thử thao tác trên bit (bitwise) Dữ liệu lưu trữ trong máy tính dưới dạng nhị phân 0 1, ví dụ: unsigned char a = 12; Thì lưu trữ dưới bộ nhớ là: 0000 1100 Tương tự unsigned int b = 95; Lưu trữ b dưới bộ nhớ là: 0000 0000 0000 0000 0000 0000 0101 1111 Không gian lưu trữ kiểu unsigned int lớn hơn unsigned char do unsigned int dùng 32 bits để biểu diễn còn unsigned char dùng 8 bits để biểu diễn. Các toán tử thao tác trên bit Trang 6
  7. Kỹ thuật dùng bit trạng thái để xử lý hiệu quả bài toán Tin học Phép thao tác trên bit Kí hiệu Phép AND & Phép OR | Phép phủ định NOT ~ Phép XOR ^ Phép dịch trái - Shift left > 2. Phép AND Kí hiệu: & Bảng chân trị A B A&B 0 0 0 0 1 0 1 0 0 1 1 1 Phép AND chỉ có giá trị 1 nếu cả hai toán hạng đều có giá trị 1. Ví dụ: A 0000 1100 B 0101 0101 C=A&B 0000 0100 3. Phép OR Kí hiệu: | Bảng chân trị A B A|B 0 0 0 Trang 7
  8. Kỹ thuật dùng bit trạng thái để xử lý hiệu quả bài toán Tin học 0 1 1 1 0 1 1 1 1 Phép OR chỉ có giá trị 0 nếu cả hai toán hạng đều có giá trị 0. Ví dụ: A 0000 1100 B 0101 0101 C=A|B 0101 1101 4. Phép phủ định NOT Kí hiệu: ~ Bảng chân trị A ~A 0 1 1 0 Phép NOT đảo bit 1 thành 0 và ngược lại. Ví dụ A 0000 1100 B = ~A 1111 0011 5. Phép XOR Kí hiệu: ^ Bảng chân trị A B A^B 0 0 0 0 1 1 1 0 1 Trang 8
  9. Kỹ thuật dùng bit trạng thái để xử lý hiệu quả bài toán Tin học 1 1 0 Phép XOR chỉ có giá trị 0 nếu cả hai toán hạng có cùng giá trị, cùng là giá trị 1, hay cùng là giá trị 0. Ví dụ A 0000 1100 B 0101 0101 C=A^B 0101 1001 6. Phép dịch trái Phép dịch phải n bit tương đương với phép chia cho 2n. Ví dụ A 0000 1100 —> B = A >> 2 0000 0011 Các ví dụ thao tác cơ bản trên bit AND unsigned char a = 5; // 00000101(5) unsigned char b = 6; // 00000110(6) unsigned char c = a & b; // 00000100(4) OR Trang 9
  10. Kỹ thuật dùng bit trạng thái để xử lý hiệu quả bài toán Tin học unsigned char a = 5; // 00000101(5) unsigned char b = 6; // 00000110(6) unsigned char c = a | b; // 00000111(7) NOT unsigned char a = 5; // 00000101(5) unsigned char b = ~a; // 11111010(250) XOR unsigned char a = 5; // 00000101(5) unsigned char b = 6; // 00000110(6) int c = a ^ b; // 00000011(3) Dịch trái unsigned char a = 5; // 00000101(5) unsigned char b = a >> 1; // 00000010(2) II. CÁC BÀI TOÁN MINH HỌA VỀ XỬ LÝ BIT TRẠNG THÁI Bài toán 1: Lấy bit Ứng dụng 1. Viết hàm getbit(x,i) cho giá trị của bit thứ i(tính từ phải sang) của số nguyên x. char Getbit(char x, i) { return (x Shr i) && 1; } Bài toán 2: Lấy số Ứng dụng 2 Viết hàm GetNum(x, j, i) cho số tạo bởi các bit tính từ trái qua phải là bit thứ j đến bit thứ i (j>=i). Trang 10
  11. Kỹ thuật dùng bit trạng thái để xử lý hiệu quả bài toán Tin học Ví dụ GetNum(103,5,1)=19 vì 103=0000 0000 0110 0111 do đó GetNum(103,5,1)= 0000 0000 0001 0011 =19 Bài giải: Gọi số lượng bit của x là L(x), trước hết ta phải hóa 0 các bit nằm ở bên trái bit thứ j. Muốn vậy ta dịch x qua trái k= L(x)-1-j bit. Sau đó ta chuyển giá trị thu được về cấu hình ban đầu tức là dịch phải k bit rồi tiếp tục dịch phải i bit để thu được số cần tìm. Hàm sizeof(x) cho ta số byte trong x. Nhân giá trị này với 8 ta sẽ được số bit trong x. Vì phép nhân 8 tương đuơng với phép dịch trái 3 bit nên sizeof(x) Shl 3 cho ta số bit trong x. Vì các bit được mã số từ phải sang trái bắt đầu từ bit 0 cho nên số hiệu cao nhất trong x sẽ là sizeof(x) Shl 3 -1 char Getnum(char x, j, i) { char k; k= (sizeof(x) Shl 3)-1-j return x Shl k Shr k Shr i; } Đối với 2 hàm Getbit và GetNum ở trên ta sé có được một số ứng dụng như chuyển từ số tự nhiên sang biểu diễn nhị phân, thập lục phân, bát phân. Ngoài ra dựa vào các phép toán logic cơ bản này ta có thể có một số ứng dụng khác như: - Viết hàm biểu diễn dưới dạng nhị phân mà không có số 0 thừa ở đầu - Viết hàm đảo trật tự các bit trong 1 số ví dụ: 1011 (11) tahnhf 1101(13) Thủ tục Batbit(x,i) gán trị 1 cho bit thứ i trong byte x Mô tả: Ta chuyển 1 đến vị trí i tương ứng sau đó thực hiện phép cộng logic với byte x Ví dụ này chỉ mang tính minh họa char Batbit(char x, i) { Trang 11
  12. Kỹ thuật dùng bit trạng thái để xử lý hiệu quả bài toán Tin học return x OR(1 Shl i); } Thu tục Tatbit(x, i) gán trị 0 cho bit thứ i trong byte Mô tả: Ta chuyển 1 đến vị trí i tương ứng, sau đó đảo byte này để được byte có 0 ở vị trí i và 1 ở các bit còn lại, cuối cùng thực hiện phép nhân logic với byte x. Ví dụ này chỉ mang tính minh họa Char Tatbit(char x, i) { return NOT(1 Shl i) And x; } Thao tác logic: giá trị bằng 0 được coi như là false (sai); giá trị khác 0 được coi như là true (đúng). Các toán tử là '!' (NOT), '&&' (AND), và '||' (OR) (không có toán tử XOR logic; nhưng có thể viết bằng NOT, AND, OR) Thao tác bit: bit 0 được coi như là false (sai); bit 1 được coi như là true (đúng). Các toán tử là '~' (NOT), '&' (AND), '|' (OR) va` '^' (XOR) Về phép dịch bit: các toán tử là '>>' (dịch qua phải) và '
  13. Kỹ thuật dùng bit trạng thái để xử lý hiệu quả bài toán Tin học left shift a by 1 right shift b by 1 return c Bài toán 4: Phép cộng Một ví dụ nữa là mã giải của phép cộng, chỉ ra cách để tính tổng của hai số nguyên a và b sử dụng các toán tử thao tác bit và phép thử số 0: while a ≠ 0 c = b and a b = b xor a left shift c by 1 a=c return b Lưu ý: các dấu = trong các ví dụ trên là phép gán chứ không phải là phép tương đương. Bài toán 5. Tập con Duyệt qua tất cả các tập con có k phần tử int s = (1 ffs(lo)) - 1 để tránh phép chia. Xác định x ? y : -y, trong đó x bằng 0 hoặc 1 (-x ^ y) + x Trang 13
  14. Kỹ thuật dùng bit trạng thái để xử lý hiệu quả bài toán Tin học Bài toán 6: Trò chơi NIM Có n đống sỏi, mỗi đống có một số viên sỏi. Hai người chơi luân phiên nhau đi như sau. Đến lượt người nào, người đó tùy chọn một đống sỏi để bốc số viên sỏi trong đống đã chọn và buộc phải bốc, ít nhất là 1 viên, nhiều nhất là cả đống. Ai bốc được những viên sỏi cuối cùng sẽ thắng. Lập chương trình tổ chức chơi giữa máy tính và người theo các yêu cầu sau: - Số lượng sỏi lúc đầu được quy định trước - Số lượng sỏi trong mỗi đống được sinh ngẫu nhiên - Máy sẽ gieo xu để xác định máy hoặc người đi trước. - Có thông báo kết quả mỗi ván. Bài giải: Có một lớp trò chơi 2 người thỏa mãn nguyên tắc sau: Tồn tại một thế có tính chất T sao cho với mọi cách đi đều dẫn đến một thế không có tính chất T mà ta kí hiệu là NT = NOT (T) và từ NT luôn luôn tìm được một cách đi để dẫn đến một thế có tính chất T. Nếu thế thắng chung cuộc có tính chất T thì ai gặp phải thế đó sẽ thua, do đó ta phải tìm mọi cách "nhường" thế có tính chất T cho đối phương. Tính chất T nói trên được gọi là bất biến của trò chơi. Khi chung cuộc mọi đống sỏi đều hết cho nên S=0. Giả sử ta có n đống sỏi. Gọi ai là số sỏi trong đống thứ i; i=1..n. Ta lấy tổng loại trừ của các ai S= a1 XOR a2 XOR .... XOR an. Ta sẽ chứng minh rằng bất biến (tính chất T) của trò chơi NIM chính là S=0. Ta sẽ sử dụng một số tính chất sau đây của phép XOR: Tính chất 1: a XOR b =0 khi và chỉ khi a=b (suy từ định nghĩa). Tính chất 2: a XOR b = b XOR a (tính giao hoán) Tính chất 3: (a XOR b) XOR c = a XOR (b XOR c) (Tính kết hợp) Tính chất 4: a XOR 0= a Ta thừa nhận định lý sau: Trang 14
  15. Kỹ thuật dùng bit trạng thái để xử lý hiệu quả bài toán Tin học Định lý: Nếu S0 thì tồn tại một ai thỏa mãn ai XOR S < ai Ta minh họa định lý trên qua ví dụ sau. Giả sử n= 3 và a1= 9= B1001 a2= 8= B1000 a3= 3= B0011 S= 2= B0010 Ta có a1 XOR S= 11>9 =a1 a2 XOR S= 10>8 = a2 a3 XOR S= 1< a3 Vậy a3 chính là số tìm được theo định lý trên Nhận xét: Nếu S=0 và có ít nhất một đống sỏi với số sỏi khác 0 thì với mọi cách đi ta luôn luôn có tổng loai trừ của các đống sỏi là một số khác 0. Thật vậy, không làm mất tính tổng quát ta giải sử rằng đống sỏi được chọn để bốc là a1. Giả sử rằng sau khi bốc đống a1 ta còn lại b1 viên sỏi. Có thế coi việc bốc sỏi là thay đống a1 bằng b1, vì a1 XOR a1= 0 nên tổng loài trừ thu được sau khi bốc sẽ là: P= b1 XOR (a2 XOR...XOR an) Nếu P = 0 thì b1=(a2 Xor ... Xor an)=0 XOR (a2 Xor...Xor an)= (a1 Xor a1) Xor (a2 Xor....Xor an)= = a1 Xor (a1 Xor a2 Xor...Xor an)= a1 Xor S. Vì S =0 nên b1 = a1 XOR 0= a1. Điều này chứng tỏ không viên sỏi nào được bốc tại đống a1, trái với luật chơi. Vậy sau khi bốc ta phải có P0 Hệ quả: Gọi S và P lần lượt là tổng loại trừ của các đống sỏi trước và sau một bước đi. Ta có, nếu S0 thì có một cách đi để P= 0; Thật vậy, theo định lý trên ta tìm được một số ai để (ai XOR S)< ai. Đặt bi = ai- (ai XOR S). Ta bốc bi viên sỏi từ đống ai, đống này sẽ còn (ai XOR S) viên. Khi đó P = (ai XOR S) XOR (ai XOR S)=0 (đpcm). Từ nhận xét và hệ quả nói trên ta suy ra S=0 chính là bất biến của trò chơi NIM. Nước đi của đối thủ thông minh khi đó sẽ bao gồm hai bước sau: Bước 1: Tính S= a1 XOR a2 XOR a3....XOR an Trang 15
  16. Kỹ thuật dùng bit trạng thái để xử lý hiệu quả bài toán Tin học Bước 2: Nếu S 0: thực hiện các bước sau: Bước 2a. Duyệt các đống sỏi để tìm đống ai thỏa điều kiện (ai XOR S)< ai Bước 2b. Bốc ai - (ai XOR S) viên từ đống ai tìm được . Số sỏi còn lại của đống này sẽ là (ai XOR S). Nếu S=0: chọn đống lớn để bốc 1 viên cốt làm cho đối phương khó phát hiện nguy cơ thua của ta. Như vậy thủ tục NIM - Trò chơi NIM với m đống sỏi gồm các bước sau Bước 1: Kiểm tra giá trị hợp lệ của m Bước 2: Khởi trị; Bước 2a. Sinh ngẫu nhiên các giá trị ai>=1, i=1..n. Bước 2b. Gieo xu để xác định ai đi trước, người hay máy Bước 3. Chơi theo sơ đồ sau Repeat If Ban then Bandi Else Maydi; Ban:= NOT Ban; Xem; Until Thua; Bước 4: Thông báo kết quả thắng- thua giữa người và máy. Trong đó thủ tục Maydi được triển khai theo sơ đồ đối thủ thông minh trình bày ở trên. Trò chơi này nhìn chung đơn giản, dễ dàng cài đặt, nếu có thêm chút đồ họa vào là quá ngon lành. Chúc các bạn thấy vui vẻ với trò chơi này. Bài toán 7. Số khác Xét một dãy gồm N số nguyên A1, A2, A3,…,AN-1, AN. Dãy có tính chất sau: Tất cả các số đều xuất hiện một số chẵn lần Có duy nhất một số x xuất hiện đúng một lần gọi là số khác. Yêu cầu: Hãy tìm số khác của một dãy cho trước. Dữ liệu vào: Trong file văn bản SK.INP gồm: Trang 16
  17. Kỹ thuật dùng bit trạng thái để xử lý hiệu quả bài toán Tin học Dòng đầu là số N (N≤107). N dòng tiếp theo, dòng thứ i là số Ai có giá trị tuyệt đối không quá 109 Ví dụ: SK.INP SK.OUT 5 1 2 1 2 3 3 Cách giải: Ta chỉ việc dùng phép toán triệt tiêu ^ để loại trừ 2 số giống nhau, khi đó kết quả sẽ là số chỉ xuất hiện 1 lần duy nhất. int kq=0,n,a; int main() { freopen("sk.inp","r",stdin); freopen("sk.out","w",stdout); ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n; for(int i=1;i>a; kq=kq^a; } cout
  18. Kỹ thuật dùng bit trạng thái để xử lý hiệu quả bài toán Tin học } Phép toán xor là phép toán triệt tiêu bit: 2 bit giống nhau cho giá trị 0; 2 bít khác nhau cho giá trị 1. Ta xét dãy n=5 số: 1, 3, 7, 3, 1 Lần 1: m=0 (tức là 00 trong hệ nhị phân); x= 1( = 01 trong hệ nhị phân) M= 0 xor 1 ( tức là 00 xor 01= 01) = 1; Lần 2: m=1 (tức là 01 trong hệ nhị phân); x= 3( = 11 trong hệ nhị phân) M= 3 xor 1 ( tức là 11 xor 01= 10) = 2; Lần 3: m=2 (tức là 01 trong hệ nhị phân); x= 7( = 111 trong hệ nhị phân) M= 7 xor 2 ( tức là 111 xor010= 101) = 5; Lần 4: m=5 (tức là 101 trong hệ nhị phân); x= 3( = 011 trong hệ nhị phân) M= 5 xor 3 ( tức là 101 xor 011= 110) = 6; Lần 5: m=6 (tức là 110 trong hệ nhị phân); x= 1( = 001 trong hệ nhị phân) M= 6 xor 1 ( tức là 110 xor 001= 111) = 7; Chú ý: dãy nhị phân 1= 0000 1=0001 2=0010 3= 0011 4=0100 5= 0101 6= 0110 7=0111 Bài toán 8. Xâu cô lập Cho trước N (N≤10000) xâu kí tự độ dài không quá 255 kí tự. Xâu cô lập được định nghĩa là xâu chỉ xuất hiện duy nhất 1 lần trong N xâu đã cho. Các xâu còn lại luôn xuất hiện một số chẵn lần. Yêu cầu: Tìm xâu cô lập từ N xâu đã cho. Với dữ liệu vào là hoàn toàn đúng đắn. Trang 18
  19. Kỹ thuật dùng bit trạng thái để xử lý hiệu quả bài toán Tin học Dữ liệu vào: Trong file văn bản SINGLE.INP gồm N dòng biểu diễn N xâu đã cho ban đầu. Kết quả ra: Ra file văn bản SINGLE.OUT xâu cô lập Ví dụ: SINGLE.INP SINGLE.OUT SINGLE.INP SINGLE.OUT -How are you? -Hello -Hello, sir. -Go away! -I am fine, thank you. -Go away! And you? -Can I help you? -I am ok. -Hello, sir. -How are you? -Can I help you? -Hello. -I am fine, thank you. And you? -I am ok. Cách giải: Cách làm như bài số khác - Dùng mảng a[300] khởi tạo bằng 0 - Đọc từng xâu vào biến xâu s + cho (i=1 đến độ dài xâu s a[i] = a[i]^s[i] Xuất kết quả: for(i=1; i
  20. Kỹ thuật dùng bit trạng thái để xử lý hiệu quả bài toán Tin học freopen("SINGLE.inp","r",stdin); freopen("SINGLE.out","w",stdout); for(i=0;i
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

EXAM.05: Bộ 300+ Đề Thi Thử THPT Quốc Gia 2022
304 tài liệu
920 lượt tải
THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2