当前位置: 代码迷 >> C语言 >> [求助]求教一道编程题???
  详细解决方案

[求助]求教一道编程题???

热度:224   发布时间:2006-08-12 03:51:40.0


对上面各位的程序做了下测试,没有一个完全正确的,仔细看了下soft_wind的,觉得写得比较好,但是存在2个问题:一个是对1的处理不当,题目要求[QUOTE](2)单独一个1写成2(0)的形式,指数上的1则不用写成这样的形式;[/QUOTE],而soft_wind一律当成2(0)处理,另一个问题是int log2(int)函数,返回的值和预想的不一致,比如log2(8)应该返回3,但实际上返回的是2,这就造成了num=8时,结果为2(2(1))+2(2(1))的情况。

针对这2个问题,我对soft_wind的程序做了下修改,测试中还没发现问题:

[CODE]#include <math.h>
char c='+'; //全局变量,用来保存数字1前面的那个符号
int log2(int num)
{
return (int)(log10(num)/log10(2));
}

void func(int num)
{
int trans;
if(num==1){
if(c=='+') //增加对1的判断
printf("2(0)");
else printf("1");
}
else if(num==2)printf("2(1)");
else {
printf("2(");
c='(';
func(log2(num));
printf(")");
trans=num-(int)pow(2,log2(num));
if(trans>0){
printf("+");
c='+';
func(trans);
}
}
}
void main()
{
int num;
start:
scanf("%d",&num);
func(num);
goto start;
getch();
}[/CODE]

测试结果:
1
2(0)
2
2(1)
3
2(1)+2(0)
4
2(2(1))
5
2(2(1))+2(0)
6
2(2(1))+2(1)
7
2(2(1))+2(1)+2(0)
8
2(2(1)+2(0))
9
2(2(1)+2(0))+2(0)
10
2(2(1)+2(0))+2(1)
11
2(2(1)+2(0))+2(1)+2(0)
12
2(2(1)+2(0))+2(2(1))
13
2(2(1)+2(0))+2(2(1))+2(0)
14
2(2(1)+2(0))+2(2(1))+2(1)
15
2(2(1)+2(0))+2(2(1))+2(1)+2(0)
16
2(2(2(1)))
17
2(2(2(1)))+2(0)
18
2(2(2(1)))+2(1)
19
2(2(2(1)))+2(1)+2(0)
20
2(2(2(1)))+2(2(1))
21
2(2(2(1)))+2(2(1))+2(0)
22
2(2(2(1)))+2(2(1))+2(1)
23
2(2(2(1)))+2(2(1))+2(1)+2(0)
24
2(2(2(1)))+2(2(1)+2(0))
25
2(2(2(1)))+2(2(1)+2(0))+2(0)
26
2(2(2(1)))+2(2(1)+2(0))+2(1)
27
2(2(2(1)))+2(2(1)+2(0))+2(1)+2(0)
28
2(2(2(1)))+2(2(1)+2(0))+2(2(1))
29
2(2(2(1)))+2(2(1)+2(0))+2(2(1))+2(0)
30
2(2(2(1)))+2(2(1)+2(0))+2(2(1))+2(1)
31
2(2(2(1)))+2(2(1)+2(0))+2(2(1))+2(1)+2(0)
64
2(2(2(1))+2(1))
97
2(2(2(1))+2(1))+2(2(2(1))+2(0))+2(0)


[此贴子已经被作者于2006-8-12 4:23:32编辑过]


----------------解决方案--------------------------------------------------------

非递归型的:
[CODE]void transact(int i)
{
switch(i){
case 0:
printf("0");
break;
case 1:
printf("2(0)");
break;
case 2:
printf("2(1)");
break;
case 3:
printf("2(1)+2(0)");
break;
case 4:
printf("2(2(1))");
break;
case 5:
printf("2(2(1))+2(0)");
break;
case 6:
printf("2(2(1))+2(1)");
break;
case 7:
printf("2(2(1))+2(1)+2(0)");
break;
case 8:
printf("2(2(1)+2(0))");
break;
case 9:
printf("2(2(1)+2(0))+2(0)");
break;
case 10:
printf("2(2(1)+2(0))+2(1)");
break;
case 11:
printf("2(2(1)+2(0))+2(1)+2(0)");
break;
case 12:
printf("2(2(1)+2(0))+2(2(1))");
break;
case 13:
printf("2(2(1)+2(0))+2(2(1))+2(0)");
break;
case 14:
printf("2(2(1)+2(0))+2(2(1))+2(1)");
break;
case 15:
printf("2(2(1)+2(0))+2(2(1))+2(1)+2(0)");
break;
case 16:
printf("2(2(2(1)))");
break;
case 17:
printf("2(2(2(1)))+2(0)");
break;
case 18:
printf("2(2(2(1)))+2(1)");
break;
case 19:
printf("2(2(2(1)))+2(1)+2(0)");
break;
case 20:
printf("2(2(2(1)))+2(2(1))");
break;
case 21:
printf("2(2(2(1)))+2(2(1))+2(0)");
break;
case 22:
printf("2(2(2(1)))+2(2(1))+2(1)");
break;
case 23:
printf("2(2(2(1)))+2(2(1))+2(1)+2(0)");
break;
case 24:
printf("2(2(2(1)))+2(2(1)+2(0))");
break;
case 25:
printf("2(2(2(1)))+2(2(1)+2(0))+2(0)");
break;
case 26:
printf("2(2(2(1)))+2(2(1)+2(0))+2(1)");
break;
case 27:
printf("2(2(2(1)))+2(2(1)+2(0))+2(1)+2(0)");
break;
case 28:
printf("2(2(2(1)))+2(2(1)+2(0))+2(2(1))");
break;
case 29:
printf("2(2(2(1)))+2(2(1)+2(0))+2(2(1))+2(0)");
break;
case 30:
printf("2(2(2(1)))+2(2(1)+2(0))+2(2(1))+2(1)");
break;
case 31:
printf("2(2(2(1)))+2(2(1)+2(0))+2(2(1))+2(1)+2(0)");
break;
default:
break;
}
}
void func(int num)
{
int flag=0;
int str[32]={0};
int i=0;
while(num>0){
str[i++]=num%2;
num/=2;
}
for(i=31;i>=0;i--)
if(str[i]){
if(flag)printf("+");
printf("2(");
transact(i);
printf(")");
flag=1;
}
}
void main()
{
int num;
start:
scanf("%d",&num);
func(num);
goto start;
getch();
}[/CODE]


----------------解决方案--------------------------------------------------------

我那个clrscr()忘记清掉了..哈

不好意思,为了自己看着舒服~

[此贴子已经被作者于2006-8-12 9:07:17编辑过]


----------------解决方案--------------------------------------------------------
楼上的测试过吗?
Please input a number(>0):3
3=2(1)(2(0))+2(0)

Please input a number(>0):8
8=2(1)(2(1)(2(0))+2(0))

这就是你的结果,完全不符合要求
----------------解决方案--------------------------------------------------------

哈哈,楼上的都帮我改好啦!
我那个程序还有个问题,当初加了getch()是来测试的,
num==2?(printf("2(1)")):(num==1?(printf("2(0)")):(printf("2("),func(log2(num)),printf(")"),trans=num-(int)pow(2,log2(num)),trans>0?(printf("+"),func(trans)):(getch())));
num==2?(printf("2(1)")):(num==1?(printf("2(0)")):(printf("2("),func(log2(num)),printf(")"),trans=num-(int)pow(2,log2(num)),trans>0?(printf("+"),func(trans)):(trans=trans)));
至于楼上的说的那个log2(8)得出结果是2,我写的时候也考虑到了,不过在运行的时候,当程序输入8的时候,
8
2(2(2(0))+2(0))
在WTC下结果是正常的,我也就没再改了,要不改成用循环递增来判断也行,只是速度慢了许多。
最后那个要求
(2)单独一个1写成2(0)的形式,指数上的1则不用写成这样的形式;
我疏忽了,谢谢指出,哈哈。..
还有,我下午写的非递归程序跟楼上的基本上是一样的,郁闷...
#include "Stdio.h"
#include "Conio.h"
#include "string.h"
void func(int *buf);
int check(int *buf,int i);
void tack(int num,char *s,char *str);
char s[400];
int pos=0;
int main(void)
{
int num,i=0;
int buf[15]={0};
scanf("%d",&num);
while(num>0)
{
buf[i++]=num%2;
num/=2;
}
func(buf);
puts(strrev(s));
getch();
return 0;
}
void func(int *buf)
{
int i,flag=1;
for(i=0;i<15&&flag;i++)
{
switch(i)
{
case 0: tack(buf[i],&s[pos],"2(0)"); break;
case 1: tack(buf[i],&s[pos],"2(1)"); break;
case 2: tack(buf[i],&s[pos],"2(2(1))"); break;
case 3: tack(buf[i],&s[pos],"2(2(2(0))+2(0))"); break;
case 4: tack(buf[i],&s[pos],"2(2(2(1)))"); break;
case 5: tack(buf[i],&s[pos],"2(2(2(1))+2(0))"); break;
case 6: tack(buf[i],&s[pos],"2(2(2(1))+2(1))"); break;
case 7: tack(buf[i],&s[pos],"2(2(2(1))+2(2(0))+2(0))"); break;
case 8: tack(buf[i],&s[pos],"2(2(2(2(0))+2(0)))"); break;
case 9: tack(buf[i],&s[pos],"2(2(2(2(0))+2(0))+2(0))"); break;
case 10:tack(buf[i],&s[pos],"2(2(2(2(0))+2(0))+2(1))"); break;
case 11:tack(buf[i],&s[pos],"2(2(2(2(0))+2(0))+2(2(0))+2(0))");break;
case 12:tack(buf[i],&s[pos],"2(2(2(2(0))+2(0))+2(2(1)))"); break;
case 13:tack(buf[i],&s[pos],"2(2(2(2(0))+2(0))+2(2(1))+2(0))");break;
case 14:tack(buf[i],&s[pos],"2(2(2(2(0))+2(0))+2(2(1))+2(1))");break;
}
if(buf[i]&&(flag=check(buf,i+1)))
sprintf(&s[pos++],"+");
}
}
int check(int *buf,int i)
{
for(;i<15;i++)
if(buf[i]) return 1;
return 0;
}
void tack(int num,char *s,char *str)
{
if(num)
{
sprintf(s,"%s",strrev(str));
pos+=strlen(str);
}
}
不过我是在WTC下,int 16bit,哈哈,少写了一半..
我测了一下,计算32767的时候,计算1000次,非递归程序计算需要0.18s,递归需要0.21s,竟然相当接近 


----------------解决方案--------------------------------------------------------
  相关解决方案