主题：第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个回复）
沙发
孤独的猫 [专家分：3370] 发布于 2006-10-11 22:33:00
不知道为什么点选了结帖后才能浏览内容(编程比赛专用选项)，还是没有隐藏回复，修改过几次，还是没用，大家先别答题，等版主来了麻烦看下，谢谢~~
板凳
overfly [专家分：3230] 发布于 2006-10-12 10:22:00
http://www.programfan.com/club/showbbs.asp?id=140327
先顶起来！
3 楼
孤独的猫 [专家分：3370] 发布于 2006-10-12 10:30:00
我按照上面发的，可还是不行，没有隐藏回复帖子，难道ＯＰＥＲＡ不行？～～
4 楼
ITER [专家分：680] 发布于 2006-10-12 22:19:00
/*********************
具体的接口不太懂 麻烦猫猫兄调整一下 呵呵
***********************/
#include <iostream>
using namespace std;
int STORE[100];//存储Fi的值,STORE[0]存储F1的值...
void deal(int C,char store[])//C为要转换的数，store存储转换后的结果
{
STORE[0]=1;
STORE[1]=3;
int i(1);
int k(0);
int biaoji(0);
while(C>STORE[i])
{
STORE[i+1]=2*STORE[i]+STORE[i-1];
i++;
}
if(C==STORE[i]||C==0)
{
if(C==0)
return ;
store[k]='1';
i--;
while(i-->=0)
store[++k]='0';
store[++k]='\0';
return ;
}
while(1)
{
if(C<STORE[i])
{
biaoji=C/STORE[i-1];
C=C-biaoji*STORE[i-1];
i--;
store[k++]=biaoji+'0';
if(C==0)
{
store[k]='\0';
return ;
}
}
}
}
main()
{
int C;
char tmp[100];
cin>>C;
deal(C,tmp);
cout<<tmp;
}
5 楼
hotzenplotz [专家分：40] 发布于 2006-10-13 09:10:00
#include "iostream.h"
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#define M 50
__int64 shuzu[M] =
{1,3,7,17,41,99,239,577,1393,3363,8119,19601,47321,114243,
275807,665857,1607521,3880899,9369319,22619537,54608393,
131836323,318281039,768398401,1855077841,4478554083,10812186007,
26102926097,63018038201,152139002499,367296043199,886731088897,
2140758220993,5168247530883,12477253282759,30122754096401,
72722761475561,175568277047523,423859315570607,1023286908188737,
2470433131948081,5964153172084899,14398739476117879,34761632124320657,
83922003724759193,202605639573839043,489133282872437279,
1180872205318713601,2850877693509864481,6882627592338442563};
int answer[M];
main()
{
memset(answer, 0, M);
__int64 a;
char ch[30];
cout << "enter the number :" <<endl;
cin >>ch;
a= _atoi64(ch);
__int64 numtemp = a;
for (int i = M-1; i >= 0; i--)
{
if (0 == numtemp)
{
break;
}
if (numtemp >= shuzu[i])
{
numtemp = numtemp - shuzu[i];
answer[i] ++;
i++;
}
}
int ntemp = 0;
for (i = M-1; i >= 0; i--)
{
if ((0 == answer[i]) && (0 == ntemp))
continue;
ntemp++;
cout << answer[i];
}
cout <<endl;
cout << "The end!" <<endl;
return;
}
6 楼
拉拉会飞 [专家分：0] 发布于 2006-10-13 09:18:00
有答案么？
7 楼
willzhanglala [专家分：1350] 发布于 2006-10-13 12:03:00
/////////////////////
//Fnum.h
template <unsigned int n>
struct Fnum
{
static const unsigned long long val=2*Fnum<n-1>::val+Fnum<n-2>::val;
};
template <>
struct Fnum<1>
{
static const unsigned long long val=1;
};
template <>
struct Fnum<2>
{
static const unsigned long long val=3;
};
#define MAX_FNUM_INDEX 51
static const unsigned long long fnum[MAX_FNUM_INDEX+1]=
{
0,
Fnum<1>::val,
Fnum<2>::val,
Fnum<3>::val,
Fnum<4>::val,
Fnum<5>::val,
Fnum<6>::val,
Fnum<7>::val,
Fnum<8>::val,
Fnum<9>::val,
Fnum<10>::val,
Fnum<11>::val,
Fnum<12>::val,
Fnum<13>::val,
Fnum<14>::val,
Fnum<15>::val,
Fnum<16>::val,
Fnum<17>::val,
Fnum<18>::val,
Fnum<19>::val,
Fnum<20>::val,
Fnum<21>::val,
Fnum<22>::val,
Fnum<23>::val,
Fnum<24>::val,
Fnum<25>::val,
Fnum<26>::val,
Fnum<27>::val,
Fnum<28>::val,
Fnum<29>::val,
Fnum<30>::val,
Fnum<31>::val,
Fnum<32>::val,
Fnum<33>::val,
Fnum<34>::val,
Fnum<35>::val,
Fnum<36>::val,
Fnum<37>::val,
Fnum<38>::val,
Fnum<39>::val,
Fnum<40>::val,
Fnum<41>::val,
Fnum<42>::val,
Fnum<43>::val,
Fnum<44>::val,
Fnum<45>::val,
Fnum<46>::val,
Fnum<47>::val,
Fnum<48>::val,
Fnum<49>::val,
Fnum<50>::val,
Fnum<51>::val,
};
// Fnum.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream>
#include "Fnum.h"
using namespace std;
int FastDetermineMaxIndex(unsigned long long num)
{
int i;
int max=52;
int min=1;
if(num==0)
return 0;
if(num==1||num==2)
return 1;
if(num==3||num==4||num==5||num==6)
return 2;
while(1)
{
i=(max+min)>>1;
if(fnum[i]>num)
max=i;
else
min=i;
if(max-min<=1)
return min;
}
}
void GetIndex(unsigned long long num, char * output )
{
int j=0;
if (num==0)
{
output[0]='0';
output[1]='\0';
return;
}
int index=FastDetermineMaxIndex(num);
if(index==51)
{
if(num>=fnum[index])
{
output[j]='1';
num-=fnum[index];
}
else
{
output[j]='0';
}
index--;
j++;
}
while(index)
{
if(num>=2*fnum[index])
{
output[j]='2';
num-=2*fnum[index];
}
else if(num>=fnum[index])
{
output[j]='1';
num-=fnum[index];
}
else
{
output[j]='0';
}
index --;
j++;
}
if(num!=0)
cout<<"calculate error\n";
output[j]='\0';
}
int main(int argc, char * argv[])
{
unsigned long long num;
if(argc<2)
{
cout<<"ERROR\n";
return 1;
}
num=0;
char * input= argv[1];
for(int i=0;input[i];i++)
{
num*=10;
num+=(input[i]-48);
}
char output[100];
GetIndex(num,output);
cout<<output<<endl;
}
8 楼
wlsss [专家分：150] 发布于 2006-10-13 12:35:00
//最多可以计算到54位数字
#include <stdio.h>
#include <string.h>
#define BIT_H04 0xf000000000000000
#define BIT_L60 0x0fffffffffffffff
#define BIT_LTH 0x1000000000000000
#define MAX_LEN 54 //2^184=2.45e55,184位数字可计算到全部54位数字
#define NUMBER 145 //((1+sqrt(2))^144+(1-sqrt(2))^144)/2=6.59e54
typedef unsigned __int64 ulong;
class uint184
{
protected:
ulong Low;
ulong Mid;
ulong High;
public:
uint184(ulong l=0,ulong m=0,ulong h=0):Low(l),Mid(m),High(h)
{
Correct();
}
uint184(char *str)
{
Low=Mid=High=0;
while(*str!='\0')
{
Low*=10;
Mid*=10;
High*=10;
Low+=(*str-'0');
Correct();
str++;
}
}
void Correct()
{
Mid+=(Low&BIT_H04)/BIT_LTH;
High+=(Mid&BIT_H04)/BIT_LTH;
Low&=BIT_L60;
Mid&=BIT_L60;
}
uint184 operator +=(uint184 &t)
{
Low+=t.Low;
Mid+=t.Mid;
High+=t.High;
Correct();
return *this;
}
uint184 operator -=(uint184 &t)
{
if(Low<t.Low)
{
Mid--;
Low+=BIT_LTH;
}
if(Mid<t.Mid)
{
High--;
Mid+=BIT_LTH;
}
High-=t.High;
Mid-=t.Mid;
Low-=t.Low;
return *this;
}
uint184 operator +(uint184 &t)
{
ulong tl=Low+t.Low;
ulong tm=Mid+t.Mid;
ulong th=High+t.High;
return uint184(tl,tm,th);
}
bool operator >=(uint184 &t)
{
return (High>t.High || (High==t.High && Mid>t.Mid) ||
(High==t.High && Mid==t.Mid && Low>=t.Low));
}
char operator/(uint184 &t)
{
char c='0';
while(*this>=t)
{
*this-=t;
c++;
}
return c;
}
};
int main(int argc, char* argv[])
{
char *str;
int i;
if(argc==1)
{
str=new char[MAX_LEN+10];
scanf("%s",str);
}
else if(argc==2)
str=argv[1];
else
{
printf("Input error!\n");
return 1;
}
int len=strlen(str);
for(i=0;i<len;i++)
{
if(str[i]<'0' || str[i]>'9')
{
printf("Not a number!\n");
return 2;
}
}
if(len>MAX_LEN)
{
printf("A large number!\n");
return 3;
}
uint184 Num(str);
uint184 F[NUMBER];
char res[NUMBER+1];
char *result=res;
F[0]=1;F[1]=3;
for(i=2;i<NUMBER;i++)
{
F[i]=F[i-1]+F[i-1]+F[i-2];
}
for(i=NUMBER-1;i>=0;i--)
{
res[NUMBER-1-i]=Num/F[i];
}
res[NUMBER]='\0';
while(*result=='0')
result++;
printf("%s\n",result);
return 0;
}
9 楼
mygoogle [专家分：500] 发布于 2006-10-13 13:29:00
tai nan la
10 楼
xieyong456 [专家分：2620] 发布于 2006-10-13 13:47:00
//我也来放个垃圾代码，哈哈[em15]
#include <stdio.h>
#define MAXNUMBER 30
#define N 26
void memorynum(int s[], int n, int num, int lim);
void print(int s[], int n);
int main(void)
{
int num[MAXNUMBER], a[N];
int F1 = 1, F2 = 3;
int i = 0, k = 0;
int flag = 1;
int count = 0;
int number;
printf("请输入你要转换的正整数 : ");
scanf("%d", &number);
while(i < N)
{
a[i++] = F1;
a[i++] = F2;
F1 = 2 * F2 + F1;
F2 = 2 * F1 + F2;
}
for(i = 0; i < N && number >= 0; i++)
{
if(number <= 10)
{
memorynum(num, k, number, count+1);
break;
}
else if(number >= a[i] && number <= a[i + 1])
{
if(number < 2 * a[i])
{
num[k++] = 1;
number -= a[i];
i = 0;
}
else if(number == a[i + 1])
{
num[k++] = 1;
count += 1;
while(count-- > 0)
{
num[k++] = 0;
}
print(num, k);
break;
}
else if(number >= 2 * a[i])
{
num[k++] = 2;
num[k++] = 0;
number -= 2 * a[i];
i = 0;
}
flag = 0;
}
else
{
if(flag == 1)
{
count++;
}
}
}
getch();
}
void print(int s[], int n)
{
int i;
for(i = 0; i < n; i++)
{
printf("%d", s[i]);
}
}
void memorynum(int s[], int n, int num, int lim)
{
int disposzero;
int i;
if(n == 0)
{
switch(num)
{
case 0 : printf("0"); break;
case 1 : printf("1"); break;
case 2 : printf("2"); break;
case 3 : printf("10"); break;
case 4 : printf("11"); break;
case 5 : printf("12"); break;
case 6 : printf("20"); break;
case 7 : printf("100"); break;
case 8 : printf("101"); break;
case 9 : printf("102"); break;
case 10: printf("110"); break;
default : printf("error");break;
}
}
else
{
switch(num)
{
case 0 :
disposzero = lim - n;
while(disposzero-- > 0)
{
s[n++] = 0;
}
break;
case 1 :
disposzero = lim - n - 1;
while(disposzero-- > 0)
{
s[n++] = 0;
}
s[n++] = 1;
break;
case 2 :
disposzero = lim - n - 1;
while(disposzero-- > 0)
{
s[n++] = 0;
}
s[n++] = 2;
break;
case 3 :
disposzero = lim - n - 2;
while(disposzero-- > 0)
{
s[n++] = 0;
}
s[n++] = 1;
s[n++] = 0;
break;
case 4 :
disposzero = lim - n - 2;
while(disposzero-- > 0)
{
s[n++] = 0;
}
s[n++] = 1;
s[n++] = 1;
break;
case 5 :
disposzero = lim - n - 2;
while(disposzero-- > 0)
{
s[n++] = 0;
}
s[n++] = 1;
s[n++] = 2;
break;
case 6 :
disposzero = lim - n - 2;
while(disposzero-- > 0)
{
s[n++] = 0;
}
s[n++] = 2;
s[n++] = 0;
break;
case 7 :
disposzero = lim - n - 3;
while(disposzero-- > 0)
{
s[n++] = 0;
}
s[n++] = 1;
s[n++] = 0;
s[n++] = 0;
break;
case 8 : disposzero = lim - n - 3;
while(disposzero-- > 0)
{
s[n++] = 0;
}
s[n++] = 1;
s[n++] = 0;
s[n++] = 1;
break;
case 9 :
disposzero = lim - n - 3;
while(disposzero-- > 0)
{
s[n++] = 0;
}
s[n++] = 1;
s[n++] = 0;
s[n++] = 2;
break;
case 10 :
disposzero = lim - n - 3;
while(disposzero-- > 0)
{
s[n++] = 0;
}
s[n++] = 1;
s[n++] = 1;
s[n++] = 0;
break;
default :
printf("error");
break;
}
}
print(s, n);
}
我来回复
您所在位置：