主题：发小学题挑战高手
tujunqiang
[专家分：150] 发布于 2005-11-15 10:47:00
印度国王的棋盘 （30分）
[问题描述]：这是一个有名的古代故事。有一个数学家发明了一种棋盘献给了印度
国王，数学家看国王非常欢喜，就向国王提出了奖赏的要求：在棋盘
的第一格放一粒米，第二格放二粒米，第三格放四粒米，第四格放八
粒米，．．．．．也就是说每一格都放进了比前一格多一倍的米。国王认为
这简直不值一提，就毫不犹豫的答应了。谁知结果却让国王大吃一惊，
当放到第64格时，就已经一共用了18446744073709551615粒米。这
在当时要几百年才能种出来。
现假定该棋盘共有200格，请你编程计算从第N格至第M 格共有
多少粒米，并以三位一撇的形式输出。
[输入]： 键盘输入整数N，M（1≤N，M≤200不用判错）。
[输出]： 精确输出从第N格至第M 格共有多少粒米，并以三位一撇的形式输出。
[样例]：输入：N，M=20，37
输出：137，438，429，184
算24 （30分）
[问题描述]
给出4个1到1000之间的整数，用这4个整数，通过+、–、*的运算而得到24，运算规则如下：
1． 每个数必须使用一次，只能使用一次
2． 运算符无优先级之分，自左向右计算。
例如：输入4个数为2，9，3，1，
则计算方法为3+9*2*1=24
[输 入]： 4个1到1000之间的整数
[输 出]： 若4个数不能产生出24，则输出error；
若能产生，则输出产生式（若有多个，仅能输出一个）。
例如：输入：1，1，2，2 输入：4，4，4，4
输出：error 输出：4*4+4+4=24
回复列表 （共11个回复）
沙发
小虾虾 [专家分：300] 发布于 2005-11-17 16:21:00
1、用高精度直接模拟
2、直接枚举
it's easy
板凳
tujunqiang [专家分：150] 发布于 2005-11-19 20:08:00
有程序吗?
3 楼
boxertony [专家分：23030] 发布于 2005-11-23 10:59:00
第一题非常简单，直接用int64计算就可以了。
(1<<M) - (1<<(N-1))
4 楼
Mcemil [专家分：1970] 发布于 2005-11-23 21:34:00
//第一题,没来得及加注释,效率也很低,大家不要见笑
#include<iostream.h>
#define N 100
void format(int a[]){
int b=N-a[0];
for(int i=N-1;i>=b;i--){
if(a[i]>=10){
a[i]=a[i]%10;
a[i-1]++;
if(i==b){
a[0]++;
}
}
}
}
void dnum(int a[]){
int i=1;
while(a[i]==0){
if(a[i]==0)
i++;
else
break;
}
a[0]=N-i;
}
void minus(int a[],int b[]){
for(int i=N-1;i>=N-a[0];i--){
if(a[i]>=b[i])
a[i]-=b[i];
else{
a[i]=a[i]+10-b[i];
a[i-1]--;
}
}
dnum(a);
}
void main(){
int n,m,num1[N],i,num2[N],j;
cout<<"M:";
cin>>m;
cout<<"N(N<=M):";
cin>>n;
for(i=1;i<N;i++){
num2[i]=0;
num1[i]=0;
}
num1[N-1]=1;num1[0]=1;
num2[N-1]=1;num2[0]=1;
for(j=1;j<=m;j++){
for(i=N-1;i>=N-num1[0];i--)
num1[i]*=2;
format(num1);
dnum(num1);
}
for(j=1;j<=n;j++){
for(i=N-1;i>=N-num2[0];i--)
num2[i]*=2;
format(num2);
dnum(num2);
}
minus(num1,num2);
cout<<endl;
for(i=N-num1[0];i<=N-1;i++){
cout<<num1[i];
}
}
5 楼
tujunqiang [专家分：150] 发布于 2005-11-23 22:11:00
能用PASCAL写吗?C我没学过[em8]
6 楼
toto061 [专家分：50] 发布于 2005-11-25 10:31:00
int64，这就是用c的好处，pascal只能用高精
7 楼
一月飘雪 [专家分：30] 发布于 2005-11-26 20:45:00
这是高精的源代码，其余自己改把：
var
s1,s2:string;
a,b:array[1..255] of integer;
c:array[1..510] of integer; {数组C用来存放结果，最大510位，为什么？}
i,j,l,m,k1,k2,x,y,z,w:integer;
begin
readln(s1); readln(s2); k1:=0;
l:=length(s1); m:=length(s2); {得到两个字符串的长度}
for i:=l downto 1 do {S1转换过程，把低位放在A[1]中}
begin
k1:=k1+1;
a[k1]:=ord(s1[i])-48;
end;
k2:=0;
for i:=m downto 1 do {S2转换过程，把低位放在B[1]中}
begin
k2:=k2+1;
b[k2]:=ord(s2[i])-48;
end;
for i:=1 to k1 do {开始计算，从低位开始乘}
for j:=1 to k2 do
begin
x:=a[i]*b[j];
y:=x div 10;
z:=x mod 10;
w:=i+j-1;
c[w]:=c[w]+z;
c[w+1]:=c[w+1]+y+c[w] div 10;
c[w]:=c[w]mod 10
end;
w:=k1+k2;
if c[w]=0 then w:=w-1; {判断最高位是否有数}
for i:=w downto 1 do write(c[i]); {输出的时候注意顺序}
writeln
end.
8 楼
yeye [专家分：40] 发布于 2005-11-30 14:04:00
int64 C++可以用吗???
再说了 2的200次方用int64 也是完全不够的呀?!~~
9 楼
friedriech [专家分：400] 发布于 2005-12-12 04:23:00
对于非常非常巨大的数字（比如300－－500位的数字）可以使用数组来表示。数组的每一个元素代表一位数字。当然加减乘除四则运算需要我们仔细编写函数实现了。
这样我们可以，用普通计算机表示极大长度的数字，并进行运算了。
10 楼
revolution20 [专家分：40] 发布于 2006-01-14 20:51:00
排列组合不是更简单吗？
我来回复
您所在位置：