Give me a hand! [Archive] - Diễn Đàn Tin Học

Pyre

08-07-2003, 22:52

Các anh chị chỉ em bài này với:
'Cho một chuỗi nhị phân được xếp vòng tròn. Sau một đơn vị thời gian chuỗi sẽ biến đổi như sau:
-Vị trí thứ i sẽ là 1 nếu ở chuỗi trước đó s[i-1] + s [i+1] = 0 hay 2.
-Vị trí thứ i sẽ là 0 nếu ở chuỗi trước đó s[i-1] + s[i+1] = 1;
Chuỗi được gọi là chết nếu tât cả các phần tử đều bằng 0;
Tìm thời gian chuỗi chết.
Input:
-Chuỗi đã cho
Output:
-Số đơn vị thời gian mà chuỗi tồn tại.(tức là sau đó sẽ chết)
-Xuất ra -1 nếu chuỗi sống mãi.

(Chú ý đây là chuỗi có cấu trúc vòng tròn.)

thanks.

Boy4is

22-07-2003, 11:25

Hí hí, pyre à, lông nhông qua đây hổng có ai giúp hết à ?? Hé hé , còn cần em chặt tay đưa cho hông ????

khôngtên

18-08-2003, 11:30

Bài này thì có gì đâu. Chỉ thực hiện như theo đề đã nói. Chẳng có gì phải gọi là !

Pyre

31-08-2003, 12:09

Bác nói xạo nó vừa vừa thui ông anh. Ông anh thử làm xem nào. Độ dài của chuỗi là 500 <--- tràn bộ nhớ là cái chắc :P
Thân
Pyre
.......................

pfiev

31-08-2003, 16:31

Bác nói xạo nó vừa vừa thui ông anh. Ông anh thử làm xem nào. Độ dài của chuỗi là 500 <--- tràn bộ nhớ là cái chắc :P
Thân
Pyre
.......................
Sao lại tràn nhỉ? Độ dài của chuỗi là 500 thì chỉ cần 500 bit, cộng thêm vài byte phụ. Dài cả tỉ vẫn đủ (tốn có 128M thôi). Còn hơn thì lưu trên đĩa.
Tuy nhiên cách làm này ko tìm ra lời giải. Phải nghĩ một thuật toán tốt hơn đã, để đối phó với trường hợp nó sống mãi. Vì nếu làm như trên với chuỗi dài n, phải cần tối đa 2^n bước để khẳng định nó sống mãi.

pfiev

31-08-2003, 16:37

À, tôi hiểu ý Pyre nói rồi. Tràn bộ nhớ nếu lưu tất cả các bước.
Lưu, vì sẽ có khả năng rất lớn là nó sẽ lặp khi chưa đến 2^n, giúp tiết kiệm được thời gian. Tuy nhiên, trường hợp xấu nhất vẫn là 2^n

Pyre

31-08-2003, 16:40

Pyre

31-08-2003, 17:12

to boy4í : wa'nh chit giờ chứ. Tui qua đây kim' cao thủ làm cho cái bài này. Dám triu tui à. Không sỡ hay seo :D :boxing:
P/S : hoá ra u cũng lông nhông giống tui à :lick:

Thân
Pyre
.....................

pfiev

31-08-2003, 18:48

Thực ra bài này tui làm được rùi (là của một người nhờ) : Đây này
http://diendantinhoc.org/forum/?action=msg&msg=1023451893&page=1
nhưng cái chính là nó làm bằng pascal nên híc. Bộ nhớ không đủ là cái chắc.
Thế mà nó cứ bắt tui phải làm đó :(
Thân
Pyre
................
Mới chạy qua đọc rồi, tuy nhiên ko thu hoạch được gì, trừ một phát hiện liên quan đến công thức xor. Tuy nhiên, cái này tui đã để ý ngay từ đầu, ko phải là xor mà là not xor. Cách tìm ra công thức có vẻ khả thi đó.
Còn về 2^n bước thì tui xin nhận xét lại: không thể nào thiếu bộ nhớ đâu (đừng lưu các bước).

Tốt nhất hiện nay là viết một chương trình thử đánh giá thời gian sống so với n (hay 2^n cũng thế). Từ đó hãy suy nghĩ hướng đi.

Pyre

31-08-2003, 19:47

to pfiev : đánh giá thế nào bây giờ! Chỉ tôi biết với! <--- hổng biết wanh giá kiểu chi cả trời.
Theo tui thì cứ đành phải lưu lại các con số nguyên tương ứng của dãy nhị phân biến đổi thui. <-- nhưng mà cách này tràn bộ nhớ là chắc ăn 100%
P/S : thui bác nghĩ cho tui đi nhá chứ tui đâu cái điền cái bài này le'm rùi :D
Thân
Pyre
.............

InstCode

04-09-2003, 15:33

Hê hê, Pyre đại sư huynh (Nam đại ca, biết nick này là ai rồi chứ ??? Đừng nói cho ai biết nghen) ... Bài này đơn giản quá mà ... tự làm đi !... he hehe ... Tui hông biết làm ! OK ????

pfiev

04-09-2003, 19:36

Hic, tui nói đánh giá là chạy với n=1 đến 20 xem nó ra các kết quả như thế nào, rồi từ đó mà ước lượng. Giống kiểu nội suy một hàm ấy.