## 495 - Fibonacci Freeze

Moderator: Board moderators

ankur_vjy
New poster
Posts: 2
Joined: Thu Jan 24, 2008 8:51 pm
i keep getting compilation error. where am i wrong ?

Code: Select all

``````#include<iostream>
#include<cmath>
#include<vector>

using namespace std;

#define MAX 1500

class BigInt {
string str;
int sign;
int len;
public:
BigInt(BigInt &b) {
str.resize(MAX);
fill(str.begin(),str.end(),'0');
str=b.str;
sign=b.sign;
len=b.len;
}
BigInt(string s) {
sign='+';
str.resize(MAX);
fill(str.begin(),str.end(),'0');
if(s[0]=='-') {
sign='-';
s[0]='0';
}
copy_backward(s.begin(),s.end(),str.end());
len=s.length();
}
BigInt() {
sign='+';
str.resize(MAX);
fill(str.begin(),str.end(),'0');
len=0;
}

BigInt operator+(BigInt B) {
BigInt sum;
int big=(len>B.len?len : B.len);
int stop=MAX-big;
int carry=0;
for(int i=MAX-1;i>=stop-1;i--) {
sum.str[i]=carry + str[i]+B.str[i] - 2*'0';
carry=sum.str[i]/10;
sum.str[i]%=10;
sum.str[i]+='0';
}
if(sum.str[stop-1]!='0')
sum.len=big+1;
else
sum.len=big;
return sum;

}
void calclen() {
int i=0;
for(i=0;str[i]=='0';i++);
len=MAX-i;
}
BigInt operator-(BigInt B) {
BigInt sum;
for(int i=MAX-len;i<MAX;i++)
B.str[i]='9'-B.str[i]+'0';
B=B+BigInt("1");
sum=*this+B;
if(sum.len>this->len) {
sum.str[MAX-sum.len]='0';
sum.len--;
}
sum.calclen();
return sum;

}

BigInt operator++() {
(*this)=(*this)+BigInt("1");
calclen();
}

BigInt operator*(BigInt B) {
BigInt prod;
for(int j=MAX-1;j>=MAX-len;j--)
prod=prod+multiply(*this,B.str[j],MAX-j-1);
prod.calclen();
return prod;
}
BigInt multiply(BigInt B, char c, int shift) {
BigInt term;
int carry=0;
for(int i=MAX-1;i>=MAX-B.len -1;i--) {
term.str[i-shift]=((B.str[i]-'0')*(c-'0') + carry)%10 + '0';
carry=((B.str[i]-'0')*(c-'0') + carry)/10;
}
term.calclen();
return term;
}
friend ostream& operator<<(ostream &stream, BigInt B);
};

ostream& operator<<(ostream &stream, BigInt B) {
if(B.len==0)
stream<<'0';
for(int i=B.str.size()-B.len;i<B.str.size();i++)
stream<<B.str[i];
return stream;
}

int main() {
int n;
while(true) {
cin>>n;
if(feof(stdin))
break;
BigInt last("1"),sLast("0");
for(int i=0;i<n-1;i++) {
BigInt temp=last;
last=last+sLast;
sLast=temp;
}
if(n==0)
last=BigInt("0");
cout<<"The Fibonacci number for "<<n<<" is "<<last<<"\n";
}
return 0;
}``````

[/code]
Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
I got the following message

Code: Select all

`````` In member function `BigInt BigInt::operator-(BigInt)':
66: no matching function for call to `BigInt::BigInt(BigInt)'
21: candidates are: BigInt::BigInt(std::basic_string<char,
std::char_traits<char>, std::allocator<char> >)
14:                 BigInt::BigInt(BigInt&)
66:   initializing argument 1 of `BigInt BigInt::operator+(BigInt)'
In member function `BigInt BigInt::operator++()':
78: no matching function for call to `BigInt::BigInt(BigInt)'
21: candidates are: BigInt::BigInt(std::basic_string<char,
std::char_traits<char>, std::allocator<char> >)
14:                 BigInt::BigInt(BigInt&)
78:   initializing argument 1 of `BigInt BigInt::operator+(BigInt)'
In member function `BigInt BigInt::operator*(BigInt)':
86: no matching function for call to `BigInt::BigInt(BigInt)'
21: candidates are: BigInt::BigInt(std::basic_string<char,
std::char_traits<char>, std::allocator<char> >)
14:                 BigInt::BigInt(BigInt&)
86:   initializing argument 1 of `BigInt BigInt::operator+(BigInt)'``````
Try erasing/commenting the following method - 'BigInt(BigInt &b)'.
turcse143
Learning poster
Posts: 81
Joined: Wed May 09, 2007 9:59 pm
---u can use 2D array for generate the
Fibonacci number.
---every row index denotes the nth Fibonacci number
---just add the previous value and set the next array.
it is fasted &easily implemented.
''I want to be most laziest person in the world''
abid_iut
Learning poster
Posts: 82
Joined: Wed Jul 16, 2008 7:34 am

### 495 need input

waht data type should i use for 5000th fibonacci number??
for problem 495:
ne one give me some tricky input???
i love to wait... wait for better... and better will come...
http://akanoi.webs.com/
sapnil
Experienced poster
Posts: 106
Joined: Thu Apr 26, 2007 2:40 pm
Location: CSE-SUST
Contact:

### Re: 495 need input

There is no special input.
plz post in right place
Thanks
Sapnil
"Dream Is The Key To Success"

@@@ Jony @@@
mesba_iutoic
New poster
Posts: 1
Joined: Sat Jun 14, 2008 1:39 am

### Re: 495 need input

You hav to do the string operation, simply bcoz there's no data type who can take more than 1000 digits.
New poster
Posts: 1
Joined: Fri Oct 03, 2008 10:38 am

### 495:fibonacci freeze ..... getting WA as verdict

plz .. check where' s the mistake
code is in c++ :

#include<iostream>
using namespace std;
int b[5001][1200]={0};
int arr[5001][1200];
void reverse(int a[][1200],int n)
{
int i=0,j;
while(a[n]!=-1) i++;
for(j=0;j<=i-1;j++) b[n][j]=a[n][i-j-1];
for(j=0;j<=i-1;j++) a[n][j]=b[n][j];
}
int main()
{

int k,z,j,i,sum,num,temp;
for(int y=1;y<5001;y++)
for(int m=0;m<1200;m++)
arr[y][m]=-1;
arr[0][0]=0;
arr[1][0]=1;
arr[2][0]=1;
for(i=3;i<5001;i++)
{
z=k=j=0;
while(arr[i-2][j]!=-1) j++;j--;
while(arr[i-1][k]!=-1) k++;k--;
while(j>=0)
{
sum=0;
sum+=arr[i-1][k]+arr[i-2][j];
j--;k--;
arr[z]=sum%10;
z++;
while(sum>=10)
{
sum/=10;
if(k>=0 && j>=0)
{sum=sum+arr[i-1][k]+arr[i-2][j];temp=sum%10;
arr[z]=temp;k--;j--;
}//if
else if(k<0) arr[z]=sum;
else if(k>=0 && j<0) {sum=sum+arr[i-1][k];
arr[z]=sum%10;k--;
}//if
z++;
}//while
if(k>=0) arr[z]=arr[i-1][k];
}
reverse(arr,i);
}
while(cin>>num)
{ i=0;
cout<<"The Fibonacci number for "<<num<<" is ";
while(arr[num]!=-1)
{
cout<<arr[num];i++;
}
cout<<endl;
}
return 0;
}
Skorpio
New poster
Posts: 2
Joined: Fri Apr 03, 2009 7:08 pm

### 495 :How can I get rid of Time limit exceed ???

Can anybody tell me, how can I get rid if time limit exceed about this problem ??
This is my code..

#include<stdio.h>
#include<string.h>

char res[2500];

int toint(char ch)
{
return (ch-'0');
}
char tochar(int c)
{
return (c+'0');
}

void reverse(char s[])
{
int i,j;

for(i=0,j=strlen(s)-1;i<j;i++,j--)
{
s^=s[j]^=s^=s[j];
}
}

{
int carry,i,j,k;
long temp,temp1,temp2;
char result[1001];

carry=0;
k=0;
for(i=strlen(s)-1,j=strlen(t)-1;i>=0 || j>=0;i--,j--,k++)
{
temp1=temp2=0;
if(i>=0)
temp1=toint(s);
if(j>=0)
temp2=toint(t[j]);
temp=temp1+temp2;
result[k]=tochar((temp+carry)%10);
carry=(carry+temp)/10;
}
while(carry!=0)
{
result[k++]=tochar(carry%10);
carry/=10;
}
result[k]='\0';
reverse(result);
}

void bigFib(long n,char res[2500])
{
char f[2000],s[2000];
long i;

f[0]='1';
f[1]='\0';
s[0]='1';
s[1]='\0';

if(n==0)
{
res[0]='0';
res[1]='\0';
}
else if(n==1 || n==2)
{
res[0]='1';
res[1]='\0';
}
else if(n>2)
{
for(i=3;i<=n;i++)
{
strcpy(f,s);
strcpy(s,res);
}
}
}

int main(void)
{
long n;

while(scanf("%ld",&n)!=EOF)
{
bigFib(n,res);
printf("The Fibonacci number for %ld is %s\n",n,res);
}
return 0;
}
ksc91u
New poster
Posts: 1
Joined: Mon Nov 02, 2009 11:35 am

### Re: 495 - Fibonacci Freeze

http://github.com/ksc91u/fibonacci_free ... bfast.java

Could not find what wrong with this.

I can compute fib 5000 = 3878968454388325633701916308325905312082127714646245106160597214895550139044037097010822916462210669479293452858882973813483102008954982940361430156911478938364216563944106910214505634133706558656238254656700712525929903854933813928836378347518908762970712033337052923107693008518093849801803847813996748881765554653788291644268912980384613778969021502293082475666346224923071883324803280375039130352903304505842701147635242270210934637699104006714174883298422891491273104054328753298044273676822977244987749874555691907703880637046832794811358973739993110106219308149018570815397854379195305617510761053075688783766033667355445258844886241619210553457493675897849027988234351023599844663934853256411952221859563060475364645470760330902420806382584929156452876291575759142343809142302917491088984155209854432486594079793571316841692868039545309545388698114665082066862897420639323438488465240988742395873801976993820317174208932265468879364002630797780058759129671389634214252579116872755600360311370547754724604639987588046985178408674382863125

38789684543883256....4382863125
MIN MAINO
New poster
Posts: 2
Joined: Wed Sep 01, 2010 2:05 pm

### what is the problem in belows Code...495_Fib_Fiz?

#include<stdio.h>
//#include<conio.h>
#define max 5000

long long d[max+1]={0};

long long fib_frz()
{
register int a;
d[0]=0;
d[1]=1;
for(a=2;a<=max;a++)
d[a]=d[a-1]+d[a-2];
return 0;
}
int main()
{
int f;
//clrscr();
fib_frz();
//freopen("in495.txt","r",stdin);
while(scanf("%d",&f)!=EOF)
printf("The Fibonacci number for %d is %lld\n",f,d[f]);
return 0;
}
MIN MAINO
New poster
Posts: 2
Joined: Wed Sep 01, 2010 2:05 pm

### [495] Fibonacci freez

#include<stdio.h>
//#include<conio.h>
#define max 5000

long long d[max+1]={0};

long long fib_frz()
{
register int a;
d[0]=0;
d[1]=1;
for(a=2;a<=max;a++)
d[a]=d[a-1]+d[a-2];
return 0;
}
int main()
{
int f;
//clrscr();
fib_frz();
//freopen("in495.txt","r",stdin);
while(scanf("%d",&f)!=EOF)
printf("The Fibonacci number for %d is %lld\n",f,d[f]);
return 0;
}
Experienced poster
Posts: 136
Joined: Sat Nov 29, 2008 8:01 am
Contact:

### Re: what is the problem in belows Code...495_Fib_Fiz?

Code: Select all

``````input :
5000

Output:

The Fibonacci number for 5000 is 3878968454388325633701916308325905312082127714646245106160597214895550139044037097010822916462210669479293452858882973813483102008954982940361430156911478938364216563944106910214505634133706558656238254656700712525929903854933813928836378347518908762970712033337052923107693008518093849801803847813996748881765554653788291644268912980384613778969021502293082475666346224923071883324803280375039130352903304505842701147635242270210934637699104006714174883298422891491273104054328753298044273676822977244987749874555691907703880637046832794811358973739993110106219308149018570815397854379195305617510761053075688783766033667355445258844886241619210553457493675897849027988234351023599844663934853256411952221859563060475364645470760330902420806382584929156452876291575759142343809142302917491088984155209854432486594079793571316841692868039545309545388698114665082066862897420639323438488465240988742395873801976993820317174208932265468879364002630797780058759129671389634214252579116872755600360311370547754724604639987588046985178408674382863125

``````

So you must use BigInteger to solve this problem.
Life is more complicated than algorithm.
http://felix-halim.net/uva/hunting.php?id=32359
noor_aub
New poster
Posts: 26
Joined: Sat Aug 22, 2009 12:16 pm

### Re: 495 - Fibonacci Freeze

What Should I Do. I am getting R/E

Code: Select all

``````#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
int main()
{
//freopen("in.txt","r",stdin);
int ind_print=3,cas=5000,p=1;
char re[10]={'0','1','2','3','4','5','6','7','8','9'};
char aa[]={'1'};
char str1[2000],str2[2000],sum[2000],str3[2000],bigstr[2000],smallstr[2000],print[5001][2000];
memset(print[0],0x0,sizeof(print[0]));
memset(print[1],0x0,sizeof(print[1]));
memset(print[2],0x0,sizeof(print[2]));
memset(str2,0x0,sizeof(str2));
memset(str3,0x0,sizeof(str3));
memset(bigstr,0x0,sizeof(bigstr));
memset(smallstr,0x0,sizeof(smallstr));
strcpy(str1,aa);
strcpy(str2,aa);
while(1)
{
//cout<<endl<<bigstr<<' '<<smallstr<<endl;
int len1,len2,big,small,ind,def,temp,temp2,sum_ind,cnt,flag,ind_str2;
len1=len2=big=small=ind=def=temp=sum_ind=cnt=temp2=flag=ind_str2=0;
len1=strlen(str1);
len2=strlen(str2);
if(len1>len2)
{
big=len1;
small=len2;
def=big-small;
strcpy(bigstr,str1);
for(ind=big-1;ind>=def;ind--)
{
smallstr[ind]=str2[small-1];
small--;
}
small=len2;
}
else if(len1<len2)
{
big=len2;
small=len1;
def=big-small;
strcpy(bigstr,str2);
for(ind=big-1;ind>=def;ind--)
{
smallstr[ind]=str1[small-1];
small--;
}
small=len1;
}
else/*If Two Number Are in Same Leangth*/
{
big=len2;
small=len1;
strcpy(bigstr,str2);
strcpy(smallstr,str1);
flag=1;
}
for(sum_ind=2000-1;;sum_ind--)
{
cnt++;
temp2=(((int)bigstr[big-1])-48)+(((int)smallstr[big-1])-48)+temp;
if(temp2>9)
{
int H=temp2%10;
sum[sum_ind]=re[H];
temp=1;
}
else
{
sum[sum_ind]=re[temp2];
temp=0;
}
big--;
if(cnt==small)
{
if(!flag)
sum_ind--;
break;
}
}
if(!flag)/*If Two Number Are in Same Leangth Then No Need to Add Second Time */
{
for(;;sum_ind--)
{
cnt++;
temp2=(((int)bigstr[big-1])-48)+temp;
if(temp2>9)
{
int H=temp2%10;
sum[sum_ind]=re[H];
temp=1;
}
else
{
sum[sum_ind]=re[temp2];
temp=0;
}
big--;
if(big==0)
break;
}
}
if(temp==1)
{
sum[sum_ind-1]='1';
cnt++;
}
strcpy(str1,str2);
for(int f=2000-cnt;f<2000;f++)
{
str3[ind_str2]=sum[f];
ind_str2++;
}
strcpy(str2,str3);
strcpy(print[ind_print],str3);
ind_print++;
cas--;
if(cas==2)
{
//printf("%s\n",str2);
break;
}
p=0;
}
int inp;
while(scanf("%d",&inp)==1)
{
int cas=inp;
if(cas>2)
printf("The Fibonacci number for %d is %s\n",cas,print[cas]);
else if(cas==1||cas==2)
printf("The Fibonacci number for %d is %d\n",cas,1);
else
printf("The Fibonacci number for %d is %d\n",cas,0);
}
return 0;
}

``````
slash190
New poster
Posts: 2
Joined: Thu Feb 10, 2011 11:52 am

### Re: 495 Why WA??

if everything is right still getting WA
try making the array size 10000 instead of 5002
wawa
New poster
Posts: 5
Joined: Thu Dec 16, 2010 8:17 am

### 495 - Fibonacct Freeze ---- Compilation error..!!!

Code: Select all

``````#include <iostream>
#include <string>
using namespace std;
string strAdd (string m, string n)
{
string result;
int stack = 0;
if (m.size() >= n.size())
{
if (m.size() > n.size())
n = "0" + n;
for (int i = n.size() - 1; i >= 0; i--)
{
if (stack != 0)
{
addition = int(m[i]) + int(n[i]) - 47;
stack = 0;
}
else
addition = int(m[i]) + int(n[i]) - 48;
{
stack++;
}
result = char (addition) + result;
}
if (stack != 0)
result = "1" + result;
}
else
return result;
}
int main()
{
string fibbo[5001];
fibbo[0] = "0";
fibbo[1] = "1";
for (int i = 2; i < 5001; i++)