[Help] Tìm chữ số thứ n trong dãy Fibonacy.

[binhan2015]

đề bài cho dãy so fibonaci xác định như sau f1=1 f2=1
f(n+1)=f(n-1)+f(n) N>=2
người ta viết liền các số trên thành dãy U như sau 11235813....
tìm chữ số thứ n tong dãy U
vd nhập n=4 thì chữ số thứ n la 3
nhập n=8 thì chữ số thứ n là 3

[fbi098]

đây là ý tưởng của mình. Bạn nào có ý tưởng hoặc thuật toán gì hay hơn thì cứ comment để mình học hỏi với [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]

Tính các giá trị fi (i chạy tới n)
mỗi lần tính xong giá trị fi thì biến nó thành string và cộng dồn vào chuỗi U cho tới khi độ dài chuỗi U = n thì dừng vòng lặp (i ko nhất thiết chạy tới n)
sau đó xuất ra kí tự cuối cùng của chuỗi U

[seodinhphong]

Bạn chủ pic cho cái giới hạn n được không? Nếu n nhỏ thì làm như skynet, nếu n mà lớn thì string không đủ, bạn dùng mảng để làm, còn về mặt thời gian mình nghĩ không đáng lo vì với n=10^6 hay 10^9 thì cùng lắm lên tới số fibo thứ mấy chục triệu, cũng là quá nhiều để làm, mà thời gian chạy test lớn cỡ đó thì bt thôi. Tốt nhất là bạn dùng free để có bộ nhớ lớn chạy test lớn, dùng thêm mảng nữa là ok.

[mallboro]

đề bài cho dãy so fibonaci xác định như sau f1=1 f2=1
f(n+1)=f(n-1)+f(n) N>=2
người ta viết liền các số trên thành dãy U như sau 11235813....
tìm chữ số thứ n tong dãy U
vd nhập n=4 thì chữ số thứ n la 3
nhập n=8 thì chữ số thứ n là 3

Dãy fi-bô-na-xi đây mà [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]
Dùng thẳng công thức tổng quát tính số thứ n (công thức Binet - tự tìm trog sách nâng cao toán 11) cho nhanh! mảng miếc tốn ô nhớ; đệ quy còn tốn hơn.

[yenyen1234]

Bạn chủ pic cho cái giới hạn n được không? Nếu n nhỏ thì làm như skynet, nếu n mà lớn thì string không đủ, bạn dùng mảng để làm, còn về mặt thời gian mình nghĩ không đáng lo vì với n=10^6 hay 10^9 thì cùng lắm lên tới số fibo thứ mấy chục triệu, cũng là quá nhiều để làm, mà thời gian chạy test lớn cỡ đó thì bt thôi. Tốt nhất là bạn dùng free để có bộ nhớ lớn chạy test lớn, dùng thêm mảng nữa là ok.

Mọi trình biên dịch 32bit đều... k phải lo lắng về chuyện ô nhớ. Tôi k nghĩ là free pascal biên dịch tốt. Ngược lại nó biên dịch chậm hơn nhiều so với BP và cũng chậm hơn VP. Mã sinh ra cũng thừa thãi, dung lượng chương trình đơn giản nhất cũng lên đến 62KB. Còn bộ Lazarus còn khủng hơn.

[incomviet]

tạo mảng các số Fibonaci sau đó tương ứng với các phần tử A trong mảng đếm số các chữ số và làm số đó thành dạng chữ và lưu thành một chuỗi kí tự ! Từ chuỗi kí tự đó xuất ra phần tử cần tìm ! Ví dụ : A[7]=13 >> khi đổi thành dạng tẽt sẽ dc 2 kí tự "1" và "3" ! Tạo một biến string trống và sau khi biến số thành text thì bạn thêm ngay vào từ đó sẽ được một chuỗi dạng text các số FIbonacy ! Bạn xuất chữ số thứ n cần tìm từ bảng đó !
---------------------------------Bài viết đã được trộn ---------------------------------
bài này giới hạn không quan trọng, quan trọng là thuật toán ! những bài pascal đa phần không làm khó bạn trong khâu giới hạn mà khó ở thuật toán ! Vì máy tính xử lí tốt các con số mà , bù lại ko ai rãnh đi tìm chữ số nào quá lớn đâu !

[thangvigreenland]

Sr bạn love nhưng bài này yêu cầu in ra CHỮ SỐ thứ N chứ không phải SỐ thứ N. Bạn đọc kĩ đã nhé. Còn bạn nói không phải lo lắng về ô nhớ thì mình không đồng tình đâu vì nếu đã không phải lo lắng thì sao mọc ra cái free pascal để làm gì?
Còn nếu bạn chủ pic thích xài ít bộ nhớ thì chẳng cần dùng tới cái gì để lưu cái đống chữ số đó đâu, chỉ cần 1 biến lưu chữ số thứ M, 1 biến có giá trị là số fibo đang xét, 1 xâu dùng trong việc tách chữ số, và vài biến linh tinh nữa (ít thôi mà) là đủ xài rồi. Tuy nhiên lúc cài đặt hơi lâu hơn chút.

[av886]

Còn bạn nói không phải lo lắng về ô nhớ thì mình không đồng tình đâu vì nếu đã không phải lo lắng thì sao mọc ra cái free pascal để làm gì?
Còn nếu bạn chủ pic thích xài ít bộ nhớ thì chẳng cần dùng tới cái gì để lưu cái đống chữ số đó đâu, chỉ cần 1 biến lưu chữ số thứ M, 1 biến có giá trị là số fibo đang xét, 1 xâu dùng trong việc tách chữ số, và vài biến linh tinh nữa (ít thôi mà) là đủ xài rồi. Tuy nhiên lúc cài đặt hơi lâu hơn chút.

Lại bắt bẻ j` nữa?
2^32 bytes ô nhớ cho FreePascal i386-win32, tức là rất rất lớn. Điều đó k có nghĩa là bạn chỉ sử dụng đc 2^32 bytes ô nhớ, với kỹ thuật lập trình dù cho là bộ 16bit như Borland Pascal bạn vẫn có thể sử dụng đc bộ nhớ ngoài. Bạn có thể sử dụng nhiều nhiều ô nhớ cho dù với hạn chế của trình biên dịch. Cái này phụ thuộc nhiều vào khả năng của người lập trình.
2^64 bytes ô nhớ cho x64 coi như là vô hạn. (Free Pascal cung cấp các trình 32 bit và 64 bit mà)

[vanphongquanphunhuan]

Lại bắt bẻ j` nữa?
2^32 bytes ô nhớ cho FreePascal i386-win32, tức là rất rất lớn. Điều đó k có nghĩa là bạn chỉ sử dụng đc 2^32 bytes ô nhớ, với kỹ thuật lập trình dù cho là bộ 16bit như Borland Pascal bạn vẫn có thể sử dụng đc bộ nhớ ngoài. Bạn có thể sử dụng nhiều nhiều ô nhớ cho dù với hạn chế của trình biên dịch. Cái này phụ thuộc nhiều vào khả năng của người lập trình.
2^64 bytes ô nhớ cho x64 coi như là vô hạn. (Free Pascal cung cấp các trình 32 bit và 64 bit mà)

Mình đâu có bắt bẻ gì, biết là kĩ thuật lập trình là then chốt, nhưng có phải ai cũng có kĩ thuật tốt đâu. bạn có thể dùng pascal thường để giải mọi bài toán, còn mình chỉ có thể giải được các bài toán trên free, điều đó đâu có sai, và đâu có thiệt hại gì? Bạn nên nhớ chủ pic mới học về pascal thôi nên không thể có kĩ thuật cao được ngay, do đó mình khuyên bạn ấy dùng free nếu muốn xử lí test lớn thôi mà.