主题：第44次编程比赛第一题~~
孤独的猫 [专家分：3370] 发布于 2006-10-12 21:50:00
已知一个数有如下递推关系~~~
[b][size=5]F[/size][/b][b][size=3]i[/size][/b][b][size=5] = [/size][/b][b][size=5]2[/size][/b][b][size=5]F[/size][/b][b][size=3]i-1[/size][/b][b][size=5] + [/size][/b][b][size=5]F[/size][/b][b][size=3]i-2[/size][/b]
设F1=1,F2=3，则有F3 = 2 x F2 + F1 = 7,F4 = 2 x F3 + F2 = 17
已经证明，由该数可以用来做一个数字系统的基，在此系统下，任一正整数都可以只用数字0，1，2来表示。
如：230 = 2 x F6 + 0 x F5 + 1 x F4 + 2 x F3 + 0 x F2 + 1 x F1
= 2 x 99 + 0 x 41 + 1 x 17 + 2 x 7 + 0 x 3 + 1 x 1
=(201201)F
168 = F6 + F5 + F4 + F3 + F2 + F1
= 99 + 41 + 17 + 7 + 3 + 1
=(111111)F
[color=FF0000]补充:如果出现一个2，则后面必须出现一个0，比如hotzenplotz提到的7可以用100也可以用21,根据这一规则,则7应该用100~~~[/color]
请编写一包含main的完整程序，并根据运行时所带的参数，输出该参数基于上面的数字系统后以0，1，2来表示的结果
如程序被编译为44.exe,则44.exe 168,此时输出111111,运行时参数所表示的数字大小不会超过(unsigned long long)的表示范围。
测试环境为gcc3.4.2
截止时间：下个星期一（10月16日）中午12点
有任何问题，请发帖讨论，或直接通过论坛发短消息给我~~
祝大家好运~~
回复列表 （共22个回复）
11 楼
独行者 [专家分：1280] 发布于 2006-10-13 15:52:00
unsigned long long a[100]={0};
int b[100]={0};
void fun(char *p,unsigned long long *t)
{
*t=0;
while(*p)
{
*t=*t*10+*p-'0';
p++;
}
}
void fun1(unsigned long long t,int *p)
{
int i;
a[1]=1;
a[2]=3;
for(i=3;a[i-1]<t;i++)
{
a[i]=2*a[i-1]+a[i-2];
}
*p=i-1;
}
void fun2(unsigned long long t,int n)
{
if(t%a[n])
{
if(t>2*a[n])
{
b[n]=2;
fun2(t-2*a[n],n-2);
}
else
if(t>a[n])
{
b[n]=1;
fun2(t-a[n],n-1);
}
else
if(t<a[n])
fun2(t,n-1);
}
else
b[n]=t/a[n];
}
void main(int argc,char *argv[])
{
unsigned long long t=0;
int n,i;
fun(argv[argc-1],&t);
fun1(t,&n);
if(t<a[n]) n--;
fun2(t,n);
for(i=n;i>0;i--)
printf("%d ",b[i]);
printf("\n");
}
12 楼
tenm [专家分：330] 发布于 2006-10-13 17:35:00
#include <stdlib.h>
#include <stdio.h>
unsigned long F(unsigned long i)
{
if(i==1) return 1;
if(i==2) return 3;
return 2*F(i-1)+F(i-2);
}
int main(int argc,char* argv[])
{
unsigned long i=1,j,k=0,l;
k=(unsigned long)atoi(argv[1]);
while(F(i)<=k){
i++;
}
i--;
for(;i>=1;i--){
j=F(i);
l=k/j;
k=k-l*j;
printf("%d",l);
}
printf("\n");
system("pause");
return 0;
}
13 楼
liren0 [专家分：260] 发布于 2006-10-13 22:45:00
#include <stdio.h>
#include <string.h>
#define MAX 100
void getdata(char *p_in);
int init_tem();
unsigned long long data_in = 0;
unsigned long long tem[MAX];
char result[MAX];
int main(int argc, char *argv[])
{
int base = 0;
int begin = 0;
if (argc != 2) return 1;
tem[1] = 1, tem[2] = 3;
getdata(argv[1]);
begin = base = init_tem();
do
{
if (tem[base] * 2 <= data_in && tem[base-1] >= data_in % (tem[base] * 2))
{
result[base] = 2;
result[base-1] = 0;
data_in = data_in % (tem[base] * 2);
base -= 2;
}
else if (tem[base] * 2 <= data_in || tem[base] <= data_in)
{
result[base] = 1;
data_in = data_in % tem[base];
base -= 1;
}
else
{
result[base] = 0;
base -= 1;
}
}while(base > 0);
while (result[begin] == 0)
begin--;
while (begin > 0)
printf("%d",result[begin--]);
return 0;
}
void getdata(char *p_in)
{
int i = strlen(p_in);
unsigned long long pow = 1;
if (i == 0) return;
i--;
while (i >= 0)
{
data_in += (*(p_in + i) - '0') * pow;
pow *= 10;
i--;
}
}
int init_tem()
{
int i = 2;
do
{
i++;
tem[i] = 2 * tem[i-1] + tem[i-2];
}while (tem[i] <= data_in);
return i-1;
}
14 楼
scanf [专家分：380] 发布于 2006-10-14 13:06:00
//我的编译环境是VC6.0
#include "stdio.h"
#include "string.h"
main(int argc, char**argv)
{
if(argc!=2)
return;
int i,len,nIndex = 1;;
unsigned __int64 F[52]={0,0x1,0x3,0x7,0x11,0x29,0x63,0xef,0x241,0x571,0xd23,0x1fb7,0x4c91,0xb8d9,0x1be43,0x4355f,0xa2901,0x188761,0x3b37c3,0x8ef6e7,0x1592591,0x3414209,0x7dba9a3,0x12f8954f,0x2dccd441,0x6e923dd1,0x1af14fe3,0x28474dd97,0x613db0b11,0xeac2af3b9,0x236c30f283,0x55848cd8bf,0xce754aa401,0x1f26f2220c1,0x4b3538ee583,0xb59163febc7,0x1b65800ebd11,0x4224165d65e9,0x9fadacc988e3,0x1817f6ff077af,0x3a2ac8caa7841,0x8c6d889456831,0x15305d9f3548a3,0x332793c7aff977,0x7b7f852e953b91,0x12a269e24da7099,0x2cfccc1784a1cc3,0x6c9c021156eaa1f,0x10634d03a3277101,0x27905a285bbd8c21,0x5f8401545aa28943,0xe6985cd111029ea7};
unsigned __int64 input = 0,temp = 0;
len = strlen(argv[1]);
for(i=0;i<len;i++)
input = input * 10 + argv[1][i] - '0';
for(;nIndex<52;nIndex++)
if(F[nIndex]>input)
break;
temp = input;
for(i=nIndex-1;i>0;i--)
if(temp>=2*F[i])
{
printf("2");
temp -= 2*F[i];
}
else if(temp>=F[i])
{
printf("1");
temp -= F[i];
}
else
printf("0");
printf("\n");
}
15 楼
heibird [专家分：60] 发布于 2006-10-15 16:00:00
周末无事可做，COBOL程序员也来凑个热闹，3年多没整这样的东东了。
#include <stdlib.h>
#include <iostream>
using namespace std;
int m_iCount; //位数
unsigned long long m_BaseValue[100]; //基本值
int m_iPre[100]; //前缀值（0，1，2）
int main(int argc, char *argv[])
{
unsigned long long inputdata = strtol(argv[1],NULL,10);
//计算基本值 、位数长度
int ix;
m_BaseValue[0] = 1;
m_BaseValue[1] = 3;
for ( ix= 2; m_BaseValue[ix-1] < inputdata; ix++)
{
m_BaseValue[ix] = 2*m_BaseValue[ix-1] + m_BaseValue[ix-2];
}
m_iCount = ix-1;
//由高位到地位循环计算各前缀值
unsigned long long iMid = inputdata;
for (ix = m_iCount; ix >= 0; ix--)
{
if (ix == 0){m_iPre[ix] = iMid;}
else if (iMid >= m_BaseValue[ix]*2){m_iPre[ix] = 2;}
else if (iMid >= m_BaseValue[ix]){m_iPre[ix] = 1;}
else {m_iPre[ix]=0;}
iMid = iMid-m_iPre[ix] * m_BaseValue[ix];
}
//输出，去掉首位0
if (m_iPre[m_iCount] == 0){ix = m_iCount - 1;}
else{ix = m_iCount;}
for(; ix>=0 ;ix--)
{
cout<<m_iPre[ix];
}
return true;
}
[em1][em1][em1][em1][em1][em1][em1]
16 楼
xylgg [专家分：800] 发布于 2006-10-15 16:27:00
我是第一次参加这总比赛,请多多指教.程序是在VC6.0下编译的,结果很好.嘿嘿!!
#include<iostream.h>
#include<stdlib.h>
int a[20];
long func(int n)
{
long f_1,f_2;
if(n<1){return 0;exit(0);}
else
{
if(n==1)return 1;
else if(n==2)return 3;
else
{
f_1=func(n-1);
f_2=func(n-2);
return(2*f_1+f_2);
}
}
}
//数的系统
void searching(long data)
{
int i=1,j=0;
int *p;
p=&a[19];
if(data==0)
{
cout<<"The searching is over"<<endl;
while((*p)==0)p--;
while(p!=a)
{
cout<<(*p);
p--;
}
cout<<endl;
exit(0);
}
else
{
while(func(i)<=data)i++;
i--;
a[i]+=1;
data=data-func(i);
searching(data);
}
}
int main(void)
{
int i=3;
long sum;
for(int j=0;j<20;j++)
a[j]=0;
cout<<"Please input the numbers needed to be calcualt:"<<endl;
cin>>sum;
searching(sum);
return 0;
}
17 楼
flypampas [专家分：30] 发布于 2006-10-15 17:27:00
#include<iostream>
#include<vector>
using namespace std;
long long double f(long long double n)
{
if(n==0) return 0;
else if(n==1) return 1;
else if(n==2) return 3;
else return 2*f(n-1)+f(n-2);
}
int main()
{
long long double x;
int i,j;
vector<long long double>a;
vector<int>b;
cout<<"输入一个整数（不为负）：\n";
cin>>x;
if(x==0)
{
cout<<x<<endl;
return 0;
}
for(i=1;x>=f(i);i++)
a.insert(a.end(),f(i));
j=i-1;
for(i=j-1;i>=0;i--)
{
if(x>=2*a[i])
{
b.insert(b.end(),2);
x-=2*a[i];
}
else if(x>=a[i])
{
b.insert(b.end(),1);
x-=a[i];
}
else
b.insert(b.end(),0);
}
cout<<"结果为：";
for(int k=0;k<j;k++)
cout<<b[k];
/* vector<int>::const_iterator it;
it=b.begin();
while(it!=b.end())
{
cout<<*it;
it++;
}*/
cout<<endl;
return 0;
}
18 楼
wyjq395 [专家分：2710] 发布于 2006-10-15 21:39:00
look！
19 楼
wyjq395 [专家分：2710] 发布于 2006-10-15 21:40:00
look！
20 楼
wshong [专家分：1880] 发布于 2006-10-16 01:58:00
#include<stdio.h>
#include<stdlib.h>
int fanu( long n)
{ long F1=1;
long F2=3;
long Fi=2*F2+F1;
int m=3;
if(n == 1)
return 1;
else if(n == 2)
return 3;
else{
while(m++<n)
{
F1=F2;
F2=Fi;
Fi=2*F2+F1;
}
return Fi;
}
}
int main()
{
long a[25];
long n;
int count=0;
char s[40];
char *p=s;
int i,j,k;
for( i=0;i<25;i++)
{
a[i]=fanu(i+1);
}
scanf("%d",&n);
for( j=0;;j++)
{
if(a[j]<=n&&a[j+1]>n)
break;
}
for( k=j;k>=0; )
{
if(n>=a[k])
{
n=n-a[k];
count++;
}
else
{ if(count==2)
{
sprintf(p,"%d",2);
p++;
sprintf(p,"%d",0);
p++;
k-=2;
}
else{
sprintf(p,"%d",count);
p++;
k--;
}
count=0;
}
}
printf("%s",s);
system("pause");
return 0;
}
呵呵，赶上最后一班车
我来回复
您所在位置：