150 Bài Toán Tin

pdf
Số trang 150 Bài Toán Tin 165 Cỡ tệp 150 Bài Toán Tin 1 MB Lượt tải 150 Bài Toán Tin 0 Lượt đọc 150 Bài Toán Tin 4
Đánh giá 150 Bài Toán Tin
4.9 ( 11 lượt)
Nhấn vào bên dưới để tải tài liệu
Đang xem trước 10 trên tổng 165 trang, để tải xuống xem đầy đủ hãy nhấn vào bên trên
Chủ đề liên quan

Nội dung

Lê Minh Hoàng 150+Bài Toán Tin Đại học Sư Phạm Hà Nội 2004 – 2006 1 LIST 150+ BÀI TOÁN TIN – LÊ MINH HOÀNG 001. TÍNH TOÁN SONG SONG 9 002. BẢNG SỐ 10 003. CARGO 11 004. DÃY CON 12 005. XÂU FIBINACCI 13 006. VÒNG SỐ NGUYÊN TỐ 14 007. ĐÔI BẠN 15 008. CỬA SỔ VĂN BẢN 16 009. VÒNG TRÒN CON 17 010. BỐ TRÍ PHÒNG HỌP 18 011. MUA VÉ TÀU HOẢ 19 012. XIN CHỮ KÝ 21 013. LẮC NẠM KIM CƯƠNG 22 014. RẢI SỎI 23 015. ĐIỆP VIÊN 24 016. KHOẢNG CÁCH GIỮA HAI XÂU 25 017. XẾP LẠI BẢNG SỐ 26 018. THĂM KHU TRIỂN LÃM 27 019. DÒ MÌN 29 020. XẾP LẠI DÃY SỐ 30 2 021. CO DÃY BÁT PHÂN 31 022. TUYẾN BAY 32 023. MÔ PHỎNG CÁC PHÉP TOÁN 33 024. DÃY CON CỦA DÃY NHỊ PHÂN 34 025. TỔNG CÁC CHỮ SỐ 35 026. ĐƯỜNG ĐI NHIỀU ĐIỂM NHẤT 36 027. KẾ HOẠCH THUÊ NHÂN CÔNG 37 028. DÃY CÁC HÌNH CHỮ NHẬT 38 029. SƠN CỘT 39 030. CẮT VẢI 40 031. CHIA KẸO 41 032. BẢNG QUAN HỆ 42 033. ĐONG NƯỚC 43 034. TRẢ TIỀN 44 035. HOÁN VỊ CHỮ CÁI 45 036. DỰ TIỆC BÀN TRÒN 46 037. TRÁO BÀI 47 038. ĐỐI XỨNG HOÁ 48 039. MẠNG MÁY TÍNH 49 040. LẬT ĐÔ MI NÔ 50 041. SỐ NHỊ PHÂN LỚN NHẤT 51 042. SƠN CÁC HÌNH CHỮ NHẬT 52 043. PHÂN HOẠCH TAM GIÁC 53 3 044. CÁC THÀNH PHẦN LIÊN THÔNG MẠNH 54 045. MÃ GRAY 55 046. DỰ ÁN XÂY CẦU 56 047. BẢO TỒN ĐỘNG VẬT HOANG DÃ 57 048. PHÁ TƯỜNG 58 049. TRUYỀN TIN TRÊN MẠNG 59 050. HÌNH VUÔNG CỰC ĐẠI 60 051. ĐOÀN XE QUA CẦU 61 052. SỐ LƯỢNG 62 053. THÁM HIỂM LÒNG ĐẤT 63 054. THỨ TỰ TỪ ĐIỂN 64 055. DÃY LỆCH 65 056. RÚT GỌN DÃY SỐ 66 057. BUÔN TIỀN 67 058. DÃY NGOẶC 68 059. THẰNG BỜM VÀ PHÚ ÔNG 69 060. SỐ THẬP PHÂN 70 061. DANH SÁCH VÒNG 71 062. TÍNH DIỆN TÍCH 72 063. THANG MÁY 73 064. TRỌNG SỐ XÂU 74 065. PHỐ MAY MẮN 75 066. TÍN HIỆU GIAO THÔNG 76 4 067. PHÂN NHÓM 77 068. TUA DU LỊCH RẺ NHẤT 78 069. DU LỊCH NHIỀU TUA NHẤT 79 070. PHÂN CÔNG 80 071. NHẮN TIN 81 072. CÁC SỐ ĐIỆN THOẠI 82 073. GIÁ TRỊ LỚN NHẤT 83 074. NÚT GIAO THÔNG TRỌNG ĐIỂM 84 075. TẬP KẾT 85 076. MỜI KHÁCH DỰ TIỆC 86 077. KHÔI PHỤC NGOẶC 87 078. DÂY XÍCH 88 079. PHÂN CÔNG 89 080. DÂY CUNG 90 081. MÊ CUNG 91 082. DU LỊCH KIỂU ÚC 92 083. SỬA ĐƯỜNG 93 084. ĐI THI 94 085. MÈO KIỂU ÚC 95 086. THÀNH PHỐ TRÊN SAO HOẢ 96 087. RÔ BỐT XÂY NHÀ 97 088. TƯ DUY KIỂU ÚC 98 089. 8-3, TẶNG HOA KIỂU ÚC 99 5 090. MÃ HOÁ BURROWS WHEELER 100 091. BAO LỒI 101 092. GIAI THỪA 102 093. PHỦ SÓNG 103 094. DÃY NGHỊCH THẾ 104 095. MUA HÀNG 105 096. XÂU CON CHUNG DÀI NHẤT 106 097. DÃY CON NGẮN NHẤT 107 098. BIẾN ĐỔI DÃY SỐ 108 099. GIÁ TRỊ NHỎ NHẤT 109 100. NỐI DÂY 110 101. GHI ĐĨA 111 102. ĐƯỜNG ĐI THOÁT MÊ CUNG 112 103. CHU TRÌNH CƠ BẢN 113 104. CỘT CÂY SỐ 114 105. LỊCH SỬA CHỮA Ô TÔ 115 106. KHỚP VÀ CẦU 116 107. HÀNG ĐỢI VỚI ĐỘ ƯU TIÊN 117 108. HỘI CHỢ 118 109. SERIE A 119 110. SỐ HIỆU VÀ GIÁ TRỊ 120 111. PHÉP CO 121 112. CHỮA NGOẶC 122 6 113. MÃ HOÁ BURROWS WHEELER 123 114. MẠNG RÚT GỌN 124 115. DÃY NGOẶC 125 116. LẮP RÁP MÁY TÍNH 126 117. ĐƯỜNG MỘT CHIỀU 127 118. PHỦ 128 119. THÁP GẠCH 129 120. THU THUẾ 130 121. PHÂN CÔNG 131 122. XÂU CON 132 123. LĂN SÚC SẮC 133 124. VỆ SĨ 134 125. GIAO LƯU 135 126. GIAO LƯU 136 127. ĐẠI DIỆN 137 128. HỘI CHỢ 138 129. LỊCH HỌC 139 130. MÃ LIÊN HOÀN 140 131. TUYỂN NHÂN CÔNG 141 132. ĐƯỜNG TRÒN 142 133. ĐOẠN 0 143 134. HỌC BỔNG 144 135. ĐOẠN DƯƠNG 145 7 136. TÍN HIỆU GIAO THÔNG 146 137. PHỦ 147 138. DI CHUYỂN RÔ-BỐT 148 139. TRẠM NGHỈ 149 140. CHIA CÂN BẰNG 151 141. LĂN XÚC XẮC 152 142. CHUYỂN HÀNG 153 143. GHÉT NHAU NÉM ĐÁ... 154 144. NỐI DÂY 155 145. MY LAST INVENTION 156 146. CÂY KHUNG NHỎ NHẤT 158 147. MẠNG MÁY TÍNH 159 148. DẴY ĐƠN ĐIỆU TĂNG DÀI NHẤT 160 149. LUỒNG CỰC ĐẠI TRÊN MẠNG 161 150. BỘ GHÉP CỰC ĐẠI 162 151. BỘ GHÉP ĐẦY ĐỦ TRỌNG SỐ CỰC TIỂU 163 152. TUYỂN NHÂN CÔNG 164 153. DÀN ĐÈN 165 8 001. TÍNH TOÁN SONG SONG Biểu thức đủ là một dãy ký tự gồm các biến ký hiệu bằng chữ cái thường tiếng Anh: a..z, các phép toán cộng ký hiệu +, nhân ký hiệu * và các dấu ngoặc (,). Được định nghĩa như sau: i) Mỗi biến a,b,...,z là một biểu thức đủ ii) Nếu X và Y là biểu thức đủ thì (X+Y) và (X*Y) cũng là biểu thức đủ. iii) Những biểu thức nào không xây dựng được theo 2 nguyên tắc trên không là biểu thức đủ. VD: Theo cách định nghĩa trên thì (a+(b+(c+d))) hoặc ((a+b)+(c*d)) là các biểu thức đủ. Cho biết thời gian tính phép + là P, thời gian tính phép * là Q, người ta định nghĩa thời gian tính toán một biểu thức đủ như sau: • Nếu biểu thức đủ chỉ gồm 1 biến (a..z) thì thời gian tính toán là 0 • Nếu X và Y là 2 biểu thức đủ; thời gian tính X là TX thời gian tính Y là TY thì thời gian tính (X+Y) là max(TX,TY)+P thời gian tính (X*Y) là max(TX,TY)+Q Từ 1 biểu thức đủ người ta có thể biến đổi về một biểu thức tương đương bằng các luật: • Giao hoán: (X+Y) ⇔ (Y+X); (X*Y) ⇔ (Y*X) • Kết hợp: (X+(Y+Z)) ⇔ ((X+Y)+Z); (X*(Y*Z)) ⇔ ((X*Y)*Z) Yêu cầu: Cho trước một biểu thức đủ E dưới dạng xâu ký tự hãy viết chương trình: 1. Tìm thời gian tính toán biểu thức E 2. Hãy biến đổi biểu thức E thành biểu thức E' tương đương với nó sao cho thời gian tính E' là ít nhất có thể. Dữ liệu vào được đặt trong file văn bản PO.INP như sau: • Dòng thứ nhất ghi 2 số P, Q cách nhau 1 dấu cách (P,Q≤100) • Tiếp theo là một số dòng, mỗi dòng ghi 1 biểu thức đủ. Kết quả ra đặt trong file văn bản PO.OUT như sau: Với mỗi biểu thức E trong file PO.INP ghi ra file PO.OUT 3 dòng • Dòng thứ nhất: Ghi thời gian tính toán E • Dòng thứ hai: Ghi biểu thức E' • Dòng thứ ba: Ghi thời gian tính toán E' Chú ý: Để cho gọn, mỗi biểu thức đủ trong input/output file có thể viết mà không cần đến cặp dấu ngoặc ngoài cùng, dữ liệu vào được coi là đúng đắn và không cần kiểm tra Ví dụ: PO.INP 1 1 a+(a+(a+(a+(a+(a+(a+a)))))) (((a+(b+(c+d)))*e)*f) (((((a*b)*c)*d)+e)+(f*g)) PO.OUT 7 ((a+a)+(a+a))+((a+a)+(a+a)) 3 5 (e*f)*((a+b)+(c+d)) 3 5 ((a*b)*(c*d))+(e+(f*g)) 3 9 002. BẢNG SỐ Cho một bảng hình chữ nhật kích thước M x N với M, N nguyên dương. M, N ≤ 50. Hình chữ nhật này được chia thành M x N ô vuông bằng nhau với kích thước đơn vị bởi các đường song song với các cạnh, trên ô vuông [i, j] ghi số nguyên A[i, j] (2 ≤ A[i, j] ≤ 50). Từ mảng A ta lập mảng B mà B[i, j] được xây dựng như sau: Biểu diễn số A[i, j] thành tổng các số nguyên tố với ràng buộc: trong biểu diễn đó có nhiều nhất chỉ một số nguyên tố xuất hiện hai lần. Trong các cách biểu diễn, chọn ra biểu diễn nhiều hạng tử nhất thì B[i, j] bằng số số hạng của biểu diễn này kể cả bội (nếu có). Ví dụ: Nếu A[i, j] = 10 = 2 + 3 + 5 thì B[i, j] = 3; Nếu A[i, j] = 12 = 2 + 2 + 3 + 5 thì B[i, j] = 4; Chú ý: Không được biểu diễn A[i, j] = 10 = 2 + 2 + 2 + 2 + 2 để có B[i, j] = 5 vì như vậy không thoả mãn ràng buộc a) Dữ liệu vào được cho bởi Text file TABLE.INP trong đó: • Dòng đầu ghi hai số M, N • M dòng sau, dòng thứ i ghi N phần tử trên dòng i của bảng A: A[i, 1], A[i, 2], ..., A[i, N] hai phần tử liên tiếp cách nhau ít nhất một dấu trống. b) Kết quả ghi ra Text file TABLE.OUT Giá trị bảng B, mỗi dòng của bảng ghi trên một dòng của file, hai phần tử liên tiếp cách nhau ít nhất một dấu trống. c) Hãy tìm hình chữ nhật lớn nhất được tạo bởi các ô mang giá trị bằng nhau của bảng B. Ghi tiếp ra file OUT.B1 một dòng gồm 5 số là: diện tích lớn nhất tìm được, toạ độ trên trái và dưới phải của hình chữ nhật có diện tích lớn nhất đó. 10
This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.