//
you're reading...
Bài tập huấn luyện, Dùng cho cấp THPT, Giáo trình chuyên Tin học 10

Tài liệu giáo khoa chuyên Tin học lớp 10 – Bài tập chuyên đề 2

Thứ tự Đề bài Hướng dẫn
2.1 Cho s là một xâu chỉ gồm 2 kí tự ‘0’ và ‘1’ mô tả một số nguyên không âm ở hệ cơ số 2, hãy chuyển số đó sang hệ cơ số 16 (độ dài xâu s không vượt quá 200). Ví dụ: 101011002=AC16 _
2.2 Cho số nguyên dương N (N<= 109).
a) Phân tích N thành thừa số nguyên tố.
b) Đếm số ước số của N.
c) Tính tổng các ước của N.
_
2.3 Đưa ra những số nhỏ hơn hoặc bằng 106 mà cách kiểm tra tính nguyên tố của Fermat bị sai. _
2.4 Sử dụng sàng số nguyên tố liệt kê các số nguyên tố trong đoạn [L,R]. _
2.5 Người ta định nghĩa một số nguyên dương N được gọi là số đẹp nếu N thỏa mãn một trong hai điều kiện sau:
a) N = 9.
b) Gọi f(N) là tổng các chữ số của N thì f(N) cũng là số đẹp.
Cho số nguyên dương N (N<= 10100), hãy kiểm tra xem N có phải là số đẹp không ?
_
2.6 Dùng cách biểu diễn số nguyên lớn bằng xâu ký tự và thêm thông tin dấu (sign=1 nếu số lớn là số không âm, sign = -1 nếu số lớn là số âm) để xử lý số nguyên lớn có dấu như sau:
type BigNum = record sign: LongInt; num: string; end;
Xem
2.7 Dùng cách biểu diễn số nguyên lớn bằng mảng (mỗi phần tử của mảng là một nhóm các chữ số).
a) Hãy xây dựng các hàm xử lí số nguyên lớn.
b) Sử dụng hàm nhân số nguyên lớn với số nguyên nhỏ để tính N! với N<= 2000.
Xem
2.8 Tìm K chữ số cuối cùng của MN), (0<K<=9, )<=M,N <=106).
Ví dụ: K=2, M=2, N= 10, ta có 210= 1024, như vậy hai chữ số cuối cùng của 210 là 24.
_
2.9 Cho N (N<= 10) nguyên dương, a1, a2, …, an,(ai <= 109). Tìm ước số chung lớn nhất, bội số chung nhỏ nhất của N số trên (chú ý, BSCNN có thể rất lớn). _
2.10 Cho hai số nguyên không âm A, B (0<= A <=B <= 10200). Tính số lượng số Fibonacci trong đoạn [A, B]. _
2.11 Cho số nguyên dương N (N <= 10100), hãy tách N thành tổng các số Fibonacci đôi một khác nhau.
Ví dụ: N = 19 = 1 + 5 +13
_
2.12 Cho N là một số nguyên dương không vượt quá 109. Hãy tìm số chữ số 0 tận cùng của N!. _
2.13 Cho s là xâu mô tả số nguyên không âm ở hệ cơ số a, hãy chuyển số đó sang hệ cơ số b (1 < a, b <= 16, độ dài xâu s không vượt quá 50). _
2.14 Xây dựng hàm kiểm tra số nguyên dương N có phải là số chính phương hay không ? (N <= 10100). _
2.15 Tính Cnk (0 < k <= N <= 2000). _
2.16 Tính số Catalann ( n <= 2000). _
2.17 Hãy đếm số cách đặt k quân xe lên bàn cớ n x n sao cho không có quân nào ăn được nhau. (1_
2.18 Giả thiết N là số nguyên dương. Số nguyên M là tổng của N với các chữ số của nó. N được gọi là nguồn của M.
Ví dụ, N =245, khi đó M = 245 + 2 + 4 + 5 = 256. Như vậy nguồn của 256 là 245. Có những số không có nguồn và có những số lại có nhiều nguồn. Ví dụ, 216 có hai nguồn là 198 và 207.
Cho số nguyên M (M có không quá 100 chữ số), hãy tìm nguồn nhỏ nhất của nó. Nếu M không có nguồn thì đưa ra số 0.
_
2.19 Tính số các ước và tổng các ước của N! (N <= 100). _
2.20 Cho một chiếc cân hai đĩa và các quả cân có khối lượng 30 , 31 , 32, … Hãy chọn các quả cân để có thể cân được vật có khối lượng N (N <= 10 100 ).
Ví dụ, cần cân vật có khối lượng N =11 ta cần sử dụng các quả cân sau:
– Đĩa cân bên trái: quả cân 31 và 32 .
– Đĩa cân bên phải: quả cân 30 và vật N = 11.
_
2.21 Đếm số lượng dãy nhị phân khác nhau độ dài n mà không có hai số 1 nào đứng cạnh nhau.
Ví dụ, n = 3, ta có 5 dãy 000, 001, 010, 100, 101.
_
2.22 Cho xâu s chỉ gồm ký tự từ ‘a’ đến ‘z’ ( độ dài xâu s không vượt quá 100), hãy đếm số hoán vị khác nhau của xâu đó.
Ví dụ, s = ‘aba’, ta có 3 hoán vị ‘aab’, ‘aba’, ‘baa’ .
_
2.23 Nam quyết định đánh số trang cho quyển sách của anh ta từ 1 đến N. Hãy tính toán số lượng chữ số 0 cần dùng, số lượng chữ số 1 cần dùng, … , số lượng chữ số 9 cần dùng.
INPUT: Tệp DIGIT.INP gồm một đòng duy nhất chứa một số N (N<= 10100).
OUTPUT: Tệp DIGIT.OUT có dạng gồm 10 dòng,

  • Dòng thứ nhất là số lượng chữ số 0 cần dùng,
  • Dòng thứ hai là số lượng chữ số 1 cần dùng,
  • Dòng thứ 10 là số lượng chữ số 9 cần dùng.
_
2.24 TAM GIÁC SỐ (Đề thi học sinh giỏi Hà Tây, năm 2006)
b2_2411Hình trên mô tả một tam giác số có số hàng N = 5. Đi từ đỉnh (số 7) đến đáy tam giác bằng một đường gấp khúc, mỗi bước chỉ được đi từ số ờ hàng trên xuống một trong hai số đứng kề bên phải hay bên trái ở hàng dưới và tính tích các số trên đường đi lại ta được một tích.Ví dụ, đường đi 7, 8, 1, 4, 6 có tích là S = 1344,
đường đi 7, 8, 1, 7, 5 có tích là S = 735.
Yêu cầu: Cho tam giác số, tìm tích của đường đi có tích lớn nhất.INPUT: Tệp văn bản TGS.INP:

  • Dòng đầu tiên chứa số nguyên n, () < n <101);
  • N dòng tiếp theo, từ dòng thứ 2 đến dòng N+1: dòng thứ i có (i-1) số cách nhau bởi dấu cách (các số có giá trị tuyệt đối không vượt quá 100).

OUTPUT: Đưa ra tệp văn bản TGS.OUT có một số nguyên là tích lớn nhất tìm được.

TGS.INP

TGS.OUT

5 5880
7
3 8
8 1 0
2 7 4 4
4 5 -2 6 5
_
2.25 HÁI NẤM (Đề thi Olimpic sinh viên, năm 2009, khối chuyên)

Một cháu gái hàng ngày được mẹ giao nhiệm vụ đến thăm bà nội. Từ nhà mình đến nhà bà nội cô bé phải đi qua một khu rừng có rất nhiều loại nấm. Trong số các loại nấm, có ba loại có thể ăn được. Cô bé đánh số ba loại nấm ăn được lần lượt là 1, 2 và 3. Là một người cháu hiếu thảo cho nên cô bé quyết định mỗi lần đến thăm bà, cô sẽ hái ít nhất hai loại nấm ăn được để nấu súp cho bà. Khu rừng mà cô bé đi qua được chia thành lưới ô vuông gồm m hàng và n cột. Các hàng của lưới được đánh số từ trên xuống dưới bắt đầu từ 1, còn các cột – đánh số từ trái sang phải, bắt đầu từ 1. Ô nằm giao của hàng i và cột j có tọa độ (i, j). Trên mỗi ô vuông, trừ ô (1, 1) và ô (m, n) các ô còn lại hoặc có nấm độc và cô bé không dám đi vào (đánh dấu là -1), hoặc là có đúng một loại nấm có thể ăn được (đánh dấu bằng số hiệu của loại nấm đó). Khi cô bé đi vào một ô vuông có nấm ăn được thì cô bé sẽ hái loại nấm mọc trên ô đó. Xuất phát từ ô (1,1), để đến được nhà bà nội ở ô (m,n) một cách nhanh nhất cô bé luôn đi theo hướng sang phải hoặc xuống dưới. Việc đi thăm bà và hái nấm trong rừng sâu gặp nguy hiểm bởi có một con chó sói luôn theo dõi và muốn ăn thịt cô bé. để phòng tránh chó sói theo dõi và ăn thịt, cô bé quyết định mỗi ngày sẽ đi theo một con đường khác nhau (hai con đường khác nhau nếu chúng khác nhau ở ít nhất một ô).

Yêu cầu: Cho bảng m×n ô vuông mô tả trạng thái khu rừng. Hãy tính số con đường khác nhau để cô bé đến thăm bà nội theo cách chọn đường đi đã nêu ở trên.

Dữ liệu: Vào từ file văn bản MUSHROOM.INP:

– Dòng đầu chứa 2 số m, n (1 < m, n <101),

– m dòng tiếp theo, mỗi dòng chứa n số nguyên cho biết thông tin về các ô của khu rừng. (riêng giá trị ở hai ô (1, 1) và ô (m, n) luôn luôn bằng 0 các ô còn lại có giá trị bằng -1, hoặc 1, hoặc 2, hoặc 3). Hai số liên tiếp trên một dòng cách nhau một dấu cách.

Kết quả: đưa ra file văn bản MUSHROOM.OUT chứa một dòng ghi một số nguyên là kết quả bài toán.

Ví dụ:

MUSHROOM.INP MUSHROOM.OUT
3 4
0 3 -1 2
3 3 3 3
3 1 3 0
3
_
2.26

HỆ THỐNG ĐÈN MÀU (Đề thi Tin học trẻ bảng B, 2009)

Để trang trí cho lễ kỉ niệm 15 năm hội thi Tin học trẻ toàn quốc, ban tổ chức đã dùng một hệ thống đèn mầu gồm n đèn đánh số từ 1 đến n. Mỗi đèn có khả năng sáng màu xanh hoặc màu đỏ. Các đèn được điều khiển theo quy tắc sau:

– Ban đầu tất cả các đèn đều sáng màu xanh.

– Sau khi kết thúc chương trình thứ nhất của lễ kỉ niệm, tất cả các đèn có số thứ tự chia hết cho 2 sẽ đổi màu…Sau khi kết thúc chương trình thứ i tất cả các đèn có số thứ tự chia hết cho i+1sẽ đổi màu (đèn xanh đổi thành màu đỏ còn đèn đỏ đổi thành màu xanh)

Minh, một thí sinh dự lễ kỉ niệm đã phát hiện được quy luật điều khiển đèn và rất thích thú với hệ thống đèn trang trí này. Vào lúc chương trình thứ k của buổi lễ vừa kết thúc, Minh đã nhẩm tính được tại thời điểm đó có bao nhiêu đèn xanh và bao nhiêu đèn đỏ. Tuy nhiên vì không có máy tính nên Minh không chắc chắn kết quả của mình là đúng. Cho biết hai số n và k (n, k ≤106) em hãy tính lại giúp Minh xem khi chương trình thứ k của buổi lễ vừa kết thúc, có bao nhiêu đèn màu đỏ.

Ví dụ với n=10; k=3.

Vậy có 4 đèn đỏ sau chương trình 3.

_
2.27 Số đẹp

Một số nguyên dương được gọi là đẹp nếu tổng bình phương các chữ số của nó (trong dạng biểu diễn thập phân) là một số nguyên tố.

Ví dụ, 12 là một số đẹp vì 12 + 22 = 5 là số nguyên tố.

Các số đẹp được đánh số theo thứ tự tăng dần của giá trị, bắt đầu từ 1.

Yêu cầu: Cho số nguyên n (1<= n <= 1000000). Hãy tìm số đẹp thứ n.

INPUT: Tệp BEAUTY.INP gồm nhiều dòng, mỗi dòng là một bộ kiểm thử chứa một số nguyên n.

OUTPUT: Tệp văn bản BEAUTY.OUT ghi kết quả của mỗi bộ kiểm thử, mỗi bộ được ghi trên một dòng.

Ví dụ:

BEAUTY. INP BEAUTY . OUT
1

6

11

23

_
2.28 Đấu giá

Thành phố Hà Nội có một số linh vật được đánh số thứ tự từ A đến B (A, B là hai số nguyên dương, A <= B). Lãnh đạo thành phố quyết định bán đấu giá những linh vật có số thứ tự đẹp để lấy tiền ủng hộ đồng bào lũ lụt miền Trung. Một số thứ tự được gọi là đẹp nếu nó thỏa mãn các điều kiện sau:

Là một số nguyên dương T mà A <= T <= B.

T là một số nguyên tố.

T là một số đối xứng (T đọc từ trái qua phải giống như đọc T từ phải qua trái). Ví dụ 12321 là một số đối xứng.

Yêu cầu: Cho hai số nguyên dương A và B (A <= B), hãy tìm số linh vật có số thứ tự đẹp.

INPUT: Tệp văn bản AUCTION.INP gồm một dòng chứa hai số nguyên dương A và B (A <= B).

OUT.PUT: Đưa ra tệp văn bản AUCTION.OUT gồm một số nguyên là số linh vật có số thứ tự đẹp.

Ví dụ:

AUCTION. INP AUCTION . OUT
1111 2222 23
_
2.29 _
2.30 _
2.31 _
2.32 _
2.33 _
2.34 _
2.35 _
2.36 _
Advertisements

About pascalteacher

Trang thông tin Toán học và Tin học

Thảo luận

Không có bình luận

Trả lời

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Đăng xuất / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Đăng xuất / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Đăng xuất / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Đăng xuất / Thay đổi )

Connecting to %s

Các tác giả

Categories

Tháng Mười 2016
H B T N S B C
« Th9   Th11 »
 12
3456789
10111213141516
17181920212223
24252627282930
31  

NCT Computer

Flickr Photos

Thống kê

  • 209,568 lượt xem

pascalteacher.nct@gmail.com


Trang huấn luyện học sinh giỏi Tin học

%d bloggers like this: