# GÓC SÁNG TẠO > Khu vực lập trình > Pascal/Delphi/Kylix >  Dãy số fibonacy!

## vuongtoan1912

Có lẽ ai trong chúng ta cũng biết đến dãy số fibonacy (được xuất phát từ một bài toán của một thương gia tên Fibonacy-bài toán cặp thỏ), giờ chúng ta hãy làm một bài toán cơ bản nho nhỏ như sau:
VCT biểu diễn số N (<=1.000.000) thành tổng các số fibonacy sao cho:
- Các số được biểu diễn theo thứ tự từ thấp đến cao, liên tục trong dãy fibonacy.
- Tổng các số là ít nhất.
 File vào: "f.inp": chứa duy nhất số N.
 File ra:"f.out":
 + Dòng đầu cho biết số lượng số fibonacy trong biểu thức.
 + Dòng thứ hai in ra các số từ cao đến thấp.
 Ví dụ: n=6. File ra sẽ là:
+ 3.
+ 3 2 1.
Lưu ý: trường hợp trên có thể viết là 5+1 nhưng không thỏa tính chất 1.
 Bài này do mình tự nghĩ ra, các bạn làm thử nhé!:emlaugh:

----------


## Lpthuylieu

bài này chị dùng quay lui , nhưng chỉ chạy đc tới 100 àhh . Sẽ cải tiến thử [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG])

----------


## Lenguyen1508

#-o



> bài này chị dùng quay lui , nhưng chỉ chạy đc tới 100 àhh . Sẽ cải tiến thử [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG])


 Chị post bài quay lui lên xem nào! học hỏi ^^. Nguyên không giải theo quay lui.!

----------


## seothamtraisan

```
const fi='fibo.inp';
      fo='fibo.out';
      a:array[1..25] of longint=(0,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025);


var   f:text;
    n:longint;
    x:array[0..100000] of longint;

procedure inp;
begin
      assign(f,fi);
      reset(f);
      readln(f,n);
      close(f);
end;

function kt(b:longint):boolean;
var   i:longint;
begin
    kt:=false;
      for i:=1 to 25 do
          if a[i]=b then
          begin
                 kt:=true;
               exit;
          end;
end;

procedure test;
var    s,k:longint;
begin
    s:=0;
      for k:=1 to n do
          s:=s+x[k];
          if s=n then
          begin
                for k:=1 to n do
                       if x[k]<>0 then write(f,x[k],' ');
                    close(f);
                    halt;
          end;
end;

procedure try(i:longint);
var   j:longint;
begin
     for j:=0 to n do
          if (j>=x[i-1]) and (kt(j)) then
          begin
               x[i]:=j;
               if i=n then test
               else try(i+1);
          end;
end;

procedure pri;
begin
     assign(f,fo);
     rewrite(f);
     x[0]:=0;
     try(1);
     close(f);
end;

begin
    inp; pri;
end.
```

10 000 ùi [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]) . Để nghĩ cách thành 100 000 [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]

----------


## toihoitoi

> ```
> const fi='fibo.inp';
>       fo='fibo.out';
>       a:array[1..25] of longint=(0,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025);
>  
>  
> var   f:text;
>     n:longint;
>     x:array[0..100000] of longint;
> ...


 Hơ! Chị sử dụng tính tay rồi viết vào tập hợp à:emlaugh: (lên đến ~75000)
Nguyên không nghĩ đến cách này [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]

----------


## tungover

tính tay j` , code thêm 1 bài fibo để tạo mảng hằng . Có sao đâu mà

----------


## iseovip5

```
const fi='FIBO.INP';
      fo='FIBO.OUT';
      x:array[1..30] of longint = (1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040);
var f:Text;
    a:array[0..30] of longint;
    n,d,c:longint;
    kt:boolean;
procedure docfile;
begin
   assign(f,fi);
   reset(f);
   readln(f,n);
   close(f);
end;

procedure xuly;
var i,j:longint;
begin
   kt:=false;
   a[1]:=x[1];
   for i:=2 to 30 do a[i]:=x[i]+a[i-1];
   for i:=1 to 30 do
      for j:=30 downto i do
         if ((a[j]-a[j-i])=n) then
            begin
               kt:=true;
               d:=j-i;c:=j;
               exit;
            end;

end;

procedure ghifile;
var i:longint;
begin
   assign(f,fo);
   rewrite(f);
   if kt then
      begin
         writeln(f,c-d);
         for i:=d+1 to c do write(f,x[i],' ');
      end
   else writeln(f,-1);
   close(f);
end;

begin
   docfile;
   xuly;
   ghifile;
end.
```

mới code xong

----------


## quechi

> ```
> const fi='FIBO.INP';
>       fo='FIBO.OUT';
>       x:array[1..30] of longint = (1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040);
> var f:Text;
>     a:array[0..30] of longint;
>     n,d,c:longint;
>     kt:boolean;
> procedure docfile;
> ...


 Đâu có trường hợp nào bị lỗi đâu mà in -1 hả bạn, xem lại đề đi nhé!

----------


## kenshin

trời , thì k có in ra -1 . Sao bắt bẻ tùm lum vậy e
Mà Hiếu ơi , nếu k có trường hợp nào nó sẽ in ra n số 1 [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]

----------


## vietbac26391

> - Các số được biểu diễn theo thứ tự từ thấp đến cao, liên tục trong dãy fibonacy.


chính bạn bảo phải biểu diễn liên tục trong dãy Fibonacy cơ mà !!!
bạn bảo ko có trường hợp nào sai thì biểu diễn số 9 thử cho tôi xem nào, nhớ phải thoả tính chất " liên tục trong dãy Fibonacy" nhe !!!
Hằng nà, đề yêu cầu là dãy liên tục mà, chỉ có 2 số 1 àh, đào đâu ra mà lắm số 1 thế [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]

----------


## Trịnh Xuân Thành

hỉu r` [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]
------------------------------------------

----------


## nhungle233

Chán thật, bài này làm trên lớp hum trước, không copy cái code về nhà (thầy bảo đúng roài nên không copy về sửa) đợi hum nào tới lớp copy về post lên các bạn coi thử. Nhưng có thuật toán này: xuất phát từ định lí, nhận xét, tiên đề hay cái gì thì kô biết nhưng có 1 điều chắc chắn là 1 số nguyên dương bao giờ cũng biểu diễn được dưới dạng tổng của các số trong dãy fibonaci. Thế thì mình không cần dùng đệ quy đâu, chỉ cần tính được mảng chứa các số fibo <= số cần biểu diễn, sau đó trừ dần số cần biểu diễn cho số đầu tiên của mảng đó (và cả việc xóa ptu đầu mảng đi nữa sau khi trừ, giảm số cần biếu diễn) tới khi nào số cần biểu diễn = 0 là ok. Thậm chí còn đảm bảo cả việc in ra đúng thứ tự Hằng yêu cầu nữa nhé. 
Nếu bạn nào đã viết code trùng với cái trên nè mình nói thì cũng đừng trách mình post lại bài nhé, cứ coi như bạn viết chương trình, mình diễn giải thuật toán (vì mình không thích đọc code đâu nên chẳng bao giờ đọc code các bạn post cả).

----------


## bedaukute22

> Chán thật, bài này làm trên lớp hum trước, không copy cái code về nhà (thầy bảo đúng roài nên không copy về sửa) đợi hum nào tới lớp copy về post lên các bạn coi thử. Nhưng có thuật toán này: xuất phát từ định lí, nhận xét, tiên đề hay cái gì thì kô biết nhưng có 1 điều chắc chắn là 1 số nguyên dương bao giờ cũng biểu diễn được dưới dạng tổng của các số trong dãy fibonaci. Thế thì mình không cần dùng đệ quy đâu, chỉ cần tính được mảng chứa các số fibo <= số cần biểu diễn, sau đó trừ dần số cần biểu diễn cho số đầu tiên của mảng đó (và cả việc xóa ptu đầu mảng đi nữa sau khi trừ, giảm số cần biếu diễn) tới khi nào số cần biểu diễn = 0 là ok. Thậm chí còn đảm bảo cả việc in ra đúng thứ tự Hằng yêu cầu nữa nhé. 
> Nếu bạn nào đã viết code trùng với cái trên nè mình nói thì cũng đừng trách mình post lại bài nhé, cứ coi như bạn viết chương trình, mình diễn giải thuật toán (vì mình không thích đọc code đâu nên chẳng bao giờ đọc code các bạn post cả).


 Ồ rất tiếc phải nói là giải thuật trên không đáp ứng được *tính liên tục*, nên sẽ có trường hợp không ra được nghiệm và phải in "-1" như bạn enlino đã code phía trên.

----------


## gahocseo

Tính liên tục nào vậy bạn? Nếu nói tính liên tục ở đây là các số trong tổng phải liên tục nhau trong dãy fibonaci thì chắc chắn 10000000% là không thể đúng toàn bộ số test (mặc dù test nhỏ vẫn ko đảm bảo được) hay đúng hơn là không thể biểu diễn được. 
VD: 10=5+3+2=8+2.
Nếu liên tục thì bạn định biểu diễn như nào???????? Hay là bạn định ghi là không biểu diễn được? Mà mình nhớ là bạn đã đưa ra trường hợp biểu diễn không tuân theo tính liên tục rồi (ngay trong bài viết đầu tiên).
Nói 1 câu thôi: biểu diễn không bắt buộc tính liên tục, bạn nào có ý kiến thì tham khảo thầy cô giáo, chắc rằng không có thầy cô nào có thuật toán đảm bảo tính liên tục đâu.

----------


## HuaAnh

> Tính liên tục nào vậy bạn? Nếu nói tính liên tục ở đây là các số trong tổng phải liên tục nhau trong dãy fibonaci thì chắc chắn 10000000% là không thể đúng toàn bộ số test (mặc dù test nhỏ vẫn ko đảm bảo được) hay đúng hơn là không thể biểu diễn được. 
> VD: 10=5+3+2=8+2.
> Nếu liên tục thì bạn định biểu diễn như nào???????? Hay là bạn định ghi là không biểu diễn được? Mà mình nhớ là bạn đã đưa ra trường hợp biểu diễn không tuân theo tính liên tục rồi (ngay trong bài viết đầu tiên).
> Nói 1 câu thôi: biểu diễn không bắt buộc tính liên tục, bạn nào có ý kiến thì tham khảo thầy cô giáo, chắc rằng không có thầy cô nào có thuật toán đảm bảo tính liên tục đâu.


bạn nói gì mình ko hỉu nhỉ
bài mình vẫn phân tích được 10 = 2 + 3 + 5
2 3 5 là 3 số nguyên tố liên tục nhau đó bạn
chả lẽ theo bạn nó ko liên tục nhau àh ??? [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG])
mà có lẽ "2 3 5" nó khác với " không biểu diễn được ? " của bạn đấy
---------------------------------Bài viết đã được trộn ---------------------------------
"Nói 1 câu thôi: biểu diễn không bắt buộc tính liên tục, bạn nào có ý kiến thì tham khảo thầy cô giáo, chắc rằng không có thầy cô nào có thuật toán đảm bảo tính liên tục đâu."

có lẽ bạn hiểu nhầm gì chăng ???
sao bài tôi vẫn biểu diễn liên tục được nhỉ ??? [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG])
nói như bạn vậy bài tôi sai te tua rồi, bạn giúp tôi sửa bài đi !!!

----------


## hungsanphuongdong

Nhưng nếu bạn biểu diễn như thế thì số lượng các số bạn dùng là kô phải nhỏ nhất, mà ở đây bạn Binhnguyen đưa ra đề bài yêu cầu là biểu diễn bởi các số fibo liên tục trong dãy, số lượng các số là nhỏ nhất. Chính cái yêu cầu đó là cái mình bảo là không thể thỏa mãn đồng thời được.

----------


## huahien

vậy là bạn quên trường hợp đặc biệt nhất rồi 
2 = 2 = 1 + 1
nếu inp là 2 thì có 2 cách phân tích, cách phân tích thành 2 là cách thoả output là các số fibonaci liên tục trong dãy và số lượng các số nhỏ nhất 
đề bài của bạn Nguyên có phá cách so với đề bài của bạn mà, bạn "*o0Tieu0Long0o*"

----------


## diemktr

Vậy rút cục nó có yêu cầu bắt buộc thỏa mãn tính liên tục không? Nếu có thì biểu diễn số nè xem nào: 15.
Dãy fibo:1 1 2 3 5 8 13 21
Ai biểu diễn liên tục được?
Các bạn còn ý kiến gì nữa không ạ?
Nếu không yêu cầu tính liên tục thì sao phải cãi nhau mãi nhỉ? Thuật toán của mình là đúng rồi.
Còn nếu bạn nói không biểu diễn được in ra -1 thì đề bài này không phù hợp cho lắm với tính chất: 1 số luôn biểu diễn được bởi tổng các số fibo. Nhưng cũng cảm ơn chủ topic đã đăng bài nè lên để cãi nhau cho đỡ buồn.

----------


## Tidus86

bạn đã cãi lấy thắng thì mình ko còn gì phải xoắn nữa [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG])
nhưng đề bài này cái yêu cầu quan trọng nhất là biểu diễn sao cho liên tục, mình tự thấy với đề của bạn Nguyên thì mình đã hoàn thành đủ 2 yêu cầu rồi, còn đề của thầy bạn cho bạn sao mình ko rõ !!!

----------


## nanivodoi

Thôi cải nhau hoài. Anh đưa ra bài này nhá, cùng Palindrome làm cho vui. [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]

*Số Palindrome*
Cho một xâu kí tự có độ dài không quá 5000 kí tự. Hãy tìm cách thêm vào xâu tại vị trí bất kì một số kí tự sao cho xâu mới tạo thành là một xâu đối xứng và số kí tự thêm vào là it nhất.
Dữ liệu vào từ file văn bản PALIN.INP, dòng đầu ghi số N, tiếp đến là xâu kí tự.
Kết quả ghi vào file văn bản PALIN.OUT gồm chỉ 1 giá trị là số kí từ cần thêm để có xâu đối xứng.
*Ghi chú:* 
Hạn chế thời gian chạy chương trình không quá 2 giây.
Cho phép sử dụng hướng dẫn dịch {$R-, C-, S-}

----------


## xuxulinh0993

```
{$H+}
const fi='PALINDROME.INP';
      fo='PALINDROME.OUT';
var f:text;
    a,b:string;
    d:array[0..5000,0..5000] of integer;
    n:integer;
procedure docfile;
var i:integer;
begin
   assign(f,fi);
   reset(f);
   readln(f,a);
   n:=length(a);
   b:='';
   for i:=n downto 1 do b:=b+a[i];
   close(f);
end;

function max(a,b,c:integer):integer;
begin
   max:=a;
   if max<b then max:=b;
   if max<c then max:=c;
end;

procedure xuly;
var i,j,k:integer;
begin
   fillchar(d,sizeof(d),0);
   for i:=1 to n do
      for j:=1 to n do
         if a[i]=b[j] then d[i,j]:=d[i-1,j-1]+1
            else d[i,j]:=max(d[i-1,j-1],d[i-1,j],d[i,j-1]);
end;

procedure ghifile;
begin
  assign(f,fo);
  rewrite(f);
  writeln(f,(n-d[n,n]));
  close(f);
end;

begin
  docfile;
  xuly;
  ghifile;
end.
```

tư tưởng : 
gọi a là chuỗi mà input đã cho 
thành lập b là chuỗi đảo ngược của a
bài toán trở về : tìm tìm xâu con chung dài nhất của 2 xâu a,b, có độ dài là m
kết quả bài toán trên là length(a)-m

----------


## sanxuattudien

> bạn đã cãi lấy thắng thì mình ko còn gì phải xoắn nữa [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG])
> nhưng đề bài này cái yêu cầu quan trọng nhất là biểu diễn sao cho liên tục, mình tự thấy với đề của bạn Nguyên thì mình đã hoàn thành đủ 2 yêu cầu rồi, còn đề của thầy bạn cho bạn sao mình ko rõ !!!


 Bạn nói thế là không đúng. Vấn đề đưa ra để mọi người cùng đưa ra hướng giải quyết, thấy đề bài ngồ ngộ thì mình có ý kiến thôi. Mình cũng có bảo đề của mình giống đề của NGuyên đâu, chỉ là cách biểu diễn như thế không hợp với khả năng biểu diễn số của dãy fibo thôi. Chẳng nhẽ ý kiến thế thôi cũng không được ah`.

----------


## anhhailua

> ```
> {$H+}
> const fi='PALINDROME.INP';
>       fo='PALINDROME.OUT';
> var f:text;
>     a,b:string;
>     d:array[0..5000,0..5000] of integer;
>     n:integer;
> procedure docfile;
> ...


Không hiểu cách của elnino ra sao nữa nhưng theo mình là bạn hiểu đề bài là tìm cách xóa đi ít nhất sao cho tạo xâu đối xứng ---> Sai đề roài.
Còn mình chưa nghĩ được cách giải.:bawling:

----------


## danghoaqt

> Không hiểu cách của elnino ra sao nữa nhưng theo mình là bạn hiểu đề bài là tìm cách xóa đi ít nhất sao cho tạo xâu đối xứng ---> Sai đề roài.
> Còn mình chưa nghĩ được cách giải.:bawling:


[IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG])
bạn thử cho test để chứng minh rằng mình sai xem nào 

mình tự hỏi xoá bớt đi 1 phần tử liệu có khác chi việc cho thêm vào 1 phần tử để "vô hiệu hoá" cái phần tử làm cho chuỗi ko đối xứng ko nhỉ ???

----------


## ledinh121189

Hôm qua ngờ ngợ thuật toán của bạn nên thử cái test này: 
9532599
Theo cách của bạn thì sẽ in ra là 5 thì phải, nhưng chính xác thì chỉ cần 2 thôi:
995323599

----------


## iseovip1

> Hôm qua ngờ ngợ thuật toán của bạn nên thử cái test này: 
> 9532599
> Theo cách của bạn thì sẽ in ra là 5 thì phải, nhưng chính xác thì chỉ cần 2 thôi:
> 995323599


- Ra 2 mà 
- Mà bạn có vẻ hay bắt bẻ ng # nhỉ. Thảo luận để giúp kiến thức của nhau tăng lên , chứ cái trò mang bài tập ra đố , bắt bẻ này nọ chẳng tốt j` cho nhau đâu .

----------


## seovietdang

QHD: f_: số lượng số ít nhất để biểu diễn i thành các số fibo
độ phức tạp là n*số lượng số fibo <=n_

----------

