Những bài toán trong Turbo Pascal

[candy]

Vì lớp 10 đang học thuật toán (Tin) mà hầu như chẳng ai hiểu gỉ.
Vì vậy sẽ mở 1 topic để bàn luận về những bài toán viết = TP
em thấy có cái topic về C+ nhưg chưa học đến, TP cho đơn giản
Mở đầu topic, e đang làm 1 bài toán = TP, nghĩ ra ý tg? nhưg nghe chừng khó thực hiện quá :-ss post lên để mngười cùng bàn ý tg? đc k a

Bt: Trò chơi bàn tròn : cho số N và dãy ai -> aN và số đếm k.
Khó nói đề bài nên e đưa VD
i 1 2 3 4 5 6 7
a 2 5 6 3 4 8 11

N là 7, số đếm chẳng hạn là 4 thì :
+ Lần 1 : a1,a2,a3,a4 (1,2,3,4) gạch a4
+ lần 2 : đêm từ a5- a6- a7- a1 (1,2,3,4 - 4 lần từ sau số bị gạch) lần này gạch a1
+ lần 3 : a2,a3,a5,a6 gạch a6
tương tự nt đến khi số cuối cùng sẽ là a2=5
Làm cách nào tìm ra số cuối cùng của dãy là a2 ạ ... ?

[siquanxoviet]

Dễ mà !
Đầu tiên ông bạn dùng lệnh lặp "while to do", chừng nào N>1 thì tăng i từ 1 đến N, mỗi lần i tăng thì lại tăng 1 biến dem.
Nếu dem = 4 thì:
1. Delete phần tử a[i], bằng cách gán liên tục a[i]:=a[i+1], a[i+1]:=a[i+2], .. , a[n-1]:=a[n];
2. Giảm N đi 1 đơn vị (N:=N-1);
3. Khởi tạo dem:=0;
Nếu i vượt quá N thì gán i bằng 1, lặp lại các thao tác trên
Khi kết thúc, giá trị duy nhất còn lại trong mảng a chỉnh là kết quả !
Nhớ phải thx đấy nhá !

[MrPaint]

Góp ý tí Học thuật toán thì ko liên quan gì đến ngôn ngữ lập trình (Pascal hay C) Ko hiểu giờ dạy ntn chứ thuật toán thường được dạy theo kiểu vẽ lưu đồ thuật toán ý (bắt đầu rồi thì input, xét điều kiện gì đấy, output, kết thúc) ~> Vậy liệu có nên sửa tên topic này đi 1 tí?

haqduong: bây giờ lên lớp ngồi đánh bài trong sgk vào anh ạ, dùng lưu đồ thì đa số các bạn hiện nay không thích còn làm kiểu liệt kê thì em không thích

[candy]

Originally Posted by MrPaint

Góp ý tí Học thuật toán thì ko liên quan gì đến ngôn ngữ lập trình (Pascal hay C) Ko hiểu giờ dạy ntn chứ thuật toán thường được dạy theo kiểu vẽ lưu đồ thuật toán ý (bắt đầu rồi thì input, xét điều kiện gì đấy, output, kết thúc) ~> Vậy liệu có nên sửa tên topic này đi 1 tí?

haqduong: bây giờ lên lớp ngồi đánh bài trong sgk vào anh ạ, dùng lưu đồ thì đa số các bạn hiện nay không thích còn làm kiểu liệt kê thì em không thích

... ok tùy a thôi

[siquanxoviet]

@haqduong: Thì sáng nay trên KITC, ông bạn candy có nói là càng đơn giản càng tốt nên em post thuật toán đơn giản, dễ hiểu nhất thôi !

[MrPaint]

Có vẻ bất cập nhì? Cơ mà ngoài thuật toán "trâu bò" kia còn có thuật toán nào để xử lý bài toán tìm phần tử cuối cùng?

Nếu chẳng may bắt mình làm thì chắc mình sẽ làm 1 boolean array, fill giá trị true Loại thằng nào thì cho nó thành false và tăng biến đếm. Khi nào đếm = n-1 thì dừng. Sau đó thì duyệt boolean array tìm index giá trị vẫn còn là true ~> tra bảng giá trị và chả lại kết quả

Any better idea?

[candy]

Originally Posted by siquanxoviet

Dễ mà !
Đầu tiên ông bạn dùng lệnh lặp "while to do", chừng nào N>1 thì tăng i từ 1 đến N, mỗi lần i tăng thì lại tăng 1 biến dem.
Nếu dem = 4 thì:
1. Delete phần tử a[i], bằng cách gán liên tục a[i]:=a[i+1], a[i+1]:=a[i+2], .. , a[n-1]:=a[n];
2. Giảm N đi 1 đơn vị (N:=N-1);
3. Khởi tạo dem:=0;
Nếu i vượt quá N thì gán i bằng 1, lặp lại các thao tác trên
Khi kết thúc, giá trị duy nhất còn lại trong mảng a chỉnh là kết quả !
Nhớ phải thx đấy nhá !

đến khi đếm > số phần từ (k>N) thì sao mô phỏng ra xem nào nghe có vẻ k ổn

[siquanxoviet]

Originally Posted by candy

đến khi đếm > số phần từ (k>N) thì sao mô phỏng ra xem nào nghe có vẻ k ổn

Khi i vượt quá n thì i sẽ quay về 1, rồi lại tăng, có gì khó hỉu đâu

[Illidan]

^ Cách làm của ku Pon (làm một array A [1..maxint] boolean rồi fill true/false) tốt hơn là mất công đếm rồi gán lại đấy =) Mà hình như cũng được luôn cho tất cả trường hợp bài này (không rõ, anh không có pascal nên chưa thử với N và K đủ to được =p). Nếu gán lại như siquan thì thời gian chạy sẽ rất rùa bò.

Bài này lên cao (trường hợp N K khổng lồ và bài toán ngược (cho biết người cuối cùng, tìm người đầu tiên)) thì có thể dùng cái gọi là danh sách liên kết (tự đọc sách, lười giải thích ). Nhưng hôm trước anh không rõ, giờ thì biết nếu chỉ là bài bình thường ở trường thôi chắc không phải để ý đến cách đấy làm gì cho phức tạp

[MrPaint]

Originally Posted by Illidan

^ Cách làm của ku Pon (làm một array A [1..maxint] boolean rồi fill true/false) tốt hơn là mất công đếm rồi gán lại đấy =) Mà hình như cũng được luôn cho tất cả trường hợp bài này (không rõ, anh không có pascal nên chưa thử với N và K đủ to được =p). Nếu gán lại như siquan thì thời gian chạy sẽ rất rùa bò.

Bài này lên cao (trường hợp N K khổng lồ và bài toán ngược (cho biết người cuối cùng, tìm người đầu tiên)) thì có thể dùng cái gọi là danh sách liên kết (tự đọc sách, lười giải thích ). Nhưng hôm trước anh không rõ, giờ thì biết nếu chỉ là bài bình thường ở trường thôi chắc không phải để ý đến cách đấy làm gì cho phức tạp

Em nghĩ dùng danh sách kết nối thì cao cấp quá Được cái chạy cực nhanh nhưng với n lớn thì bộ nhớ không biết thế nào mà lần Có lần dùng danh sách kết nối tìm số nguyên tố rồi theo dõi bộ nhớ mới thấy là...

Tóm lại, mọi người xem cách dùng bảng tham chiếu boolean thôi

[quan]

Anh paint vs anh dương chỉ cho em mấy cái thuật toán liên thông vs ah, em đọc chẳng hiểu gì cả.
@ Dương: đội tuyển học sau tiết 3 thứ 4 nhá! Anh bỏ hơi bị lắm rồi đêy!!

[Mikoto]

Anh paint vs anh dương chỉ cho em mấy cái thuật toán liên thông vs ah

Eto... liên thông có phải là loang rộng và loang sâu không? Bây giờ cấp 3 trường mình cũng phải học cái đấy rồi à o.o" vãi nhỉ :d

[MrPaint]

Kinh quá, mình thề là mình chưa nghe đến thuật toán liên thông bao giờ ý Các em bây giờ còn đi học đội tuyển, thật là kinh khủng quá đi Hic hic. Thấy nuối tiếc cho bản thân

[Illidan]

Kinh quá, mình thề là mình chưa nghe đến thuật toán liên thông bao giờ ý

Anh tưởng chỉ dân đen thôi chứ Admin mà cũng phét à

[MrPaint]

Originally Posted by Illidan

Anh tưởng chỉ dân đen thôi chứ Admin mà cũng phét à

Ơ, hem biết thật +_+ Vừa đi Google có tí sáng tỏ Tìm liên thông thì chơi vừa rộng vừa sâu chắc là ra thôi nhỉ Cơ mà thế thì độ phức tạp cũng khiếp No idea

[haqduong]

Originally Posted by quan

Anh paint vs anh dương chỉ cho em mấy cái thuật toán liên thông vs ah, em đọc chẳng hiểu gì cả.
@ Dương: đội tuyển học sau tiết 3 thứ 4 nhá! Anh bỏ hơi bị lắm rồi đêy!!

Thằng ku Đức nó không báo anh em ạ Thằng này nó không báo anh coi như nghỉ
Còn vấn đề liên thông: em đọc sách nào thế? liên thông thì cứ bfs || dfs mà chơi, tùy bài