1/ Điền số Cho một bảnh 2 chiều kích thước n*n. Hãy thực hiện điền các số nguyên dương vào bảng theo quy luật sau : - Ô (1,1) (góc trái trên) bằng 1. - Thứ tự điền theo dòng từ trên xuống và theo cột từ trái sang phải. - Giá trị điền vào ô tại dòng i, cột j phải là số nhỏ nhất chưa xuất hiện tron dòng i và cột j VD : với n=5 1 2 3 4 5 2 1 4 3 Số nhỏ nhất chưa xuất hiện trên dòng 2 và cột 4 là 3 KQ : 1 2 3 4 5 2 1 4 3 6 3 4 1 2 7 4 3 2 1 8 5 6 7 8 1 Có ai rảnh rảnh solve giúp em mấy đề này với ... 2/ Số đối xứng Một số được gọi là số đối xứng khi các chữ số của nó đối xứng qua tâm. Ví dụ : 5, 44, 212, 71217. Cho một số x = 371, số đối xứng lớn hơn và gần x nhất là 373. Yêu cầu : cho một số nguyên dương x (x có số chữ số <= 100), hãy tìm số đối xứng lớn hơn và gần x nhất. 3/ Tập sinh Cho một tập T gồm n số nguyên dương, các số có thể trùng nhau. Hãy chọn ra một tập S nhỏ nhất các số trong T sao cho mọi số trong T đều có thể viết dưới dạng tổng các số trong S. Dữ liệu vào từ file văn bản TAPSINH.INP -Dòng đầu là số n (n<=1000) -n dòng tiếp theo là n số nguyên dương a1,a2,... an (a1<=10000 , i = 1...n)
mịe hỏi thế này thì đ. ai trả lời được !!! Đề thi là dùng ngôn ngữ lập trình nào chứ: Pascal, C, C++, VB,... !
Bài 1: uses crt; var n,i,j,try:integer; a:array[1..100,1..100] of integer; function kt:boolean; var m:integer; begin kt:=true; for m:= 1 to i-1 do if a[m,j] = a[i,j] then begin kt:=false; exit; end; for m:= 1 to j-1 do if a[i,m] = a[i,j] then begin kt:=false; exit; end; end; begin clrscr; write('Nhap N: '); readln(n); a[1,1]:=1; for i:=1 to n do a[1,i]:=i; for i:=2 to n do for j:=1 to n do begin try:=0; repeat inc(try); a[i,j]:=try; until kt; end; for i:=1 to n do begin for j:=1 to n do write(a[i,j]:5); writeln; end; readln; end.
Bài 2 thì nói thuật toán thui nhé vì tận 100 chữ số nên dùng luôn biến s (string) để lưu số Thuật toán: đầu tiên cho s = x Dần dần tăng s lên 1 đơn vị rồi làm 1 function kiểm tra xem nó có đối xứng ko Thuật toán đối xứng giả sử cho xâu là đối xứng. Sau đó: for i:= 0 to (length(s) div 2) do if s[i+1] <> s[length(s) - i) then (ko phải đối xứng) Bài 3 bạn thử nêu 1 ví dụ nhé
làm cách đấy lâu quá, nhỡ số nó 1 tỉ tỉ hay lớn hơn nữa thì ngồi cộng 1 dần thì có dùng c2d hay quadcore cũng có mà đến tết, mà đã chuyển thành string rồi thì cộng 1 thế nào được nữa, mà có cộng được cũng dính overflow ngay nếu không dùng double(tận 100 chữ số) trong trường hợp giả thuyết, trường hợp xấu nhất là 10^100 phép tính, trường hợp xấu nhất thực tế có thể dễ dàng lên đến 10^50-1 phép tính vd. 99999...90000 (50 số 9, 50 số 0) nhìn vào thấy ngay số đối xứng gần nhất là 9999..999(100 số 9), nhưng nếu cộng dần 1 thì phải cộng từ 000...000 lên 9999...9999 máy tính nhanh nhất bây giờ là 360 teraflops tức là 360*10^12 phép tính một giây, để tính được 10^50 phép tính với double thì mất khoảng 3*10^37 giây, tuổi của vũ trụ hiện tại là 4.3*10^17 giây (13.7 tỉ năm) cho nên cách cộng 1 có thể giải quyết được với những số nhỏ, còn đề bài cho số tận 100 chữ số thì không thể dùng cách này được, hiệu suất quá thấp. cách tớ chọn là parse chữ số đấy thành 1 string, kiểm tra xem string đấy có bao nhiêu char, nếu lẻ thì cắt ra làm 2 phần bằng nhau, bỏ số chính giữa, nếu chẵn thì chỉ việc cắt đôi sau đấy đặt 2 giá trị trong 2 string mới thành float (giờ chỉ còn tối đa 50 chữ số trong 1 số nên dùng float được) nếu số bên trái lớn hơn số bên phải thì đơn giản, chỉ cần cho giá trị số bên phải bằng số bên trái rồi đổi 2 số trở lại thành string rồi gộp lại chuyển qua dạng double là xong nếu số bên trái lại nhỏ hơn số bên phải thì cộng một vào số bên trái rồi cho số bên phải bằng số bên trái, tiếp tục các bước gộp 2 số, trở lại thành string rồi parse ngược trở lại double thuật toán k0 có gì khó, nhưng mà trước giờ tớ chỉ code bằng java với python, pascal bao nhiêu năm rồi không đụng đến nữa nên chỉ có thể nói thuật toán được thôi
Lâu oy` ko đụng đến Pascal nhưng theo ý kiến thì đề thi năm nay cũng vừa tầm. Đề 1 & 2 ko khó lắm, vừa đọc lướt qua nên chưa dám đưa ra thuật toán nào vì chưa làm thử, nó ko tốt thì ... . Nhưng nói chung thì cái thuật toán bài 2 của Raegonex thì có vẻ rất tốt vs những test vừa thử vs notepad . Còn thuật toán của ông hacker_IT thì xin lỗi là ... vứt đi . Thôi để các cao thủ bàn tiếp, đang suy nghĩ thử bài 3
đối với bài 2 cho hỏi là nếu như số đó là 1259652 thì dùng string làm sao nhỉ?đâu thể tăng lên một số nữa đâu. nó sẽ đưa đến " : " mất=
là lính mới và cũng đang mày mò pascal nên xin chỉ giáo nhiều. mong các đại ca nói rõ giùm float là gì và đối với bài 2 thì bài giải cụ thể như thế nào
float là kiểu thực, int là nguyên, double lớn hơn float đại loại thế . ___________Auto Merge________________ . bài 3 cao siêu quá chả hiểu đề
ToanAZ ở Đồng Nai à ? Hớ hớ, anh là Đào, giải 1 Đồng Nai - tin học trẻ không chuyên năm 2001 Giải 2 Toàn quốc phần mềm 1998 ^^ Cho anh gửi lời hỏi thâm đến cô - Nhà thiếu nhi Đồng Nai Thầy gì Mập mập nhé, lâu quá, anh quên hết cả tên Anh học dưới anh Ngôn 1 năm
Bạn dùng đệ qui này để tăng xâu lên một đơn vị nè procedure incstr(k:integer); begin if s[k]='9' then begin s[k]:'0'; incstr(k-1); end else s[k]:=char(ord(s[k])+1); end; Nhưng mà mình không dùng cái này để mỗi lần lặp rồi kiểm tra xâu này có đối xứng hay không, Nếu dùng như vậy chỉ cần 20 chữ số là đến tết rồi chớ nói gì đến 100 chữ số. mình dùng cách xét, như vậy chương trình sẽ thông minh hơn, chứ không ngu như cách tăng. Với lại chấp cho ban tổ chức ra 200 chứ số cũng không ngán, chương trình cũng chạy chưa tới 1/1000 giây. Mọi người thử nha. Năm nay nếu hên thì mình cũng được đi thi.
óc óc óc khỏi nói nhìu có khi thèng học đại học cntt 4 năm cũng rớt với cái đề tào lao mía ghim này thoai....
về bài thứ 2 tớ đưa ra thuật toán thế này: đầu tiên chia đưa số về chuỗi. chia đôi chuỗi rồi xem nó có gần đối xứng không, và có khả năng đối xứng khi nâng 1,2,3... 1 nghìn đơn vị hay không. nếu có, xuất ra số gần nhất. nếu không, nhích vị trí chính giữa lên một đơn vị, giờ đây ta có 2 phần không bằng nhau, lệch nhau 1 chữ số. Bây giờ thêm một chữ số vào cuối dãy số để được dãy bằng dãy trước. lại kiểm tra xem có đối xứng hay không. tiếp tục cho đến khi số chính giữa hiện tại là số cuối của số ban đầu thì ngừng.
bài 2 thì dùng đảo ngược số đi, nếu số sau khi đảo ngược bằng y chang số lúc đầu thì nó là đối xứng....... xét gần x nhất và lớn hơn x thì dùng for xét lên, gặp số nào đối xứng thì dừng.......(dùng break, ko dùng break thì càng tốt)......
đã chạy (N^2), trong mỗi n^2 lại chạy thêm từ 1 đến hơn N, tình hình là k ổn, nên đặt cận để giảm độ phức tạp, nếu hay hơn thì sẽ thấy ma trận kết quả đối xứng
