标题:一个做题的思路
只看楼主
icanbestrong
Rank: 3Rank: 3
等 级:论坛游侠
帖 子:100
专家分:138
注 册:2013-3-13
结帖率:50%
 问题点数:0 回复次数:0 
一个做题的思路
我做一道题的思路,当然题很简单,可能会让大神们见笑了,不过大神们不也是从我这种小菜鸟开始的吗?希望可以或多或少的对大家有所启发,也算是再次激励我自己吧!!!
   还是要从我看得一个问题说起。问题如下:用1,3,9,27,81五个数通过加减运算组合出1到121之间的任意一个整数。乍看之下好像不可能,但仔细推敲以后发现这是可行的,比如23,23=27-3
-1,106=81+27-1等等。可惜这个题需要通过编程实现。那麽问题就来了,如何实现之?人脑可以毫不费力的几秒钟组合出来,虽然貌似没有一定的规律性。如何将人脑中的思路系统地变换成
计算机语言,这又是遇到的第二个大问题。在经过多番寻找规律后依旧一无所获,于是乎差点就放弃。(其实也没怎麽想,就是闲来无聊时想想)某天,应该是在最近,忽然想到,没有办法就
用不是办法的办法,用最笨的办法:穷举法。对于人脑来说,如若需要穷举,且穷举项很多的话,就会很占“大脑内存”,那麽之前的很容易忘掉,造成混乱。而计算机相对来说可用内存很大,
但关键是它没有主动性。也就是说它不知道该怎麽想,(所以科幻里说计算机若智能一点,那就比人还聪明,后果会相当可怕),由此才产生了各种各类的方法来引导计算机。题外的提一句,
大家现在用的计算机或者说是电子设备的所有功能,都是算法,也就是设计者早就具有了的想法,是不是很具有超前性?扯回主题来说,所以如若人与计算机优势互补一下的话,那怎麽说呢,
创造的成就那会是相当牛逼的。实践是检验真理的唯一标准,我们的时代和之前漫长的人类进化史相比,文明增长率可要搞之前几十或几百倍。当然,如若人类文明不倒退的话,要是之后还发
明了更好的智慧工具,那高我们这个时代几百倍甚至几千倍也会是正常的。(好奇心永远是推动社会进步的最更本动力,所以我们才会越来越聪明)貌似又扯远了,我的意思很简单就是,计算机
的产生是推动我们这个时代进步的根本源泉,也就是人们说的第三次工业革命,“信息时代”。而对于我这个渺小的问题来说(虽然说的有点慷慨激昂,但高楼万丈拔地起嘛),我最大的失误就
是把它当作一道数学题来解了,只把它当作一道传统的数学题来解了,而忽视了我的好朋友computer的作用。(我敢说若干年后中小学生一定会用计算机做数量级更大,难度更大的数学题,可能
在我的有生之年是等不到这一天的到来了,但我坚信这绝不会是信口开河)尝试了很多想法以后,我还是觉得文章的穷举法才有可行性。我的想法如下:
  问题上说了就是这五个数当中多个进行加减运算,那麽我们就可以得到这样一个式子,给定1~121之间任意一个数n,n=a1*b1*1+a2*b2*3+a3*b3*9+a4*b4*27+a5*b5*81.其中a1~a5分别取值为0,1。
表示该项是否存在,这是借鉴拉格朗日插值中l的开关效应而想出来的。而b1~b5各自取值为-1或1,刚开始想到的是用加减号来代替b1~b5的值,来表示各项的正负,可这样就不好通过语言实现之,
于是就用乘以正负1来代替了。好了,现在式子是有了,但对于n来说,唯一不确定的就是每个字母到底该取各自可能值的哪个。通过上面的介绍后,不难发现,总共有十个位置,(十个字母),
每个位置的取值情况都为两种,(0或1,-1或1),即两种状态,这就好比相当于有十枚硬币,只不过这些硬币不尽相同,单号的可能是一块钱的,双号的可能就是五毛或一毛的了,但抛出后产生
的情况还是2的10次方中,即1024种情况。而其中会有些情况是符合要求的,只要找出一种就完成任务咯。貌似穷举量很大,但别担心,我有好盆友。现在又来问题了,如何模拟这1024种情况,目测
很头疼但对于我们这些专业的来说可能就不是问题。可以设想有十个位置,每个位置两种可能性的话,可以用0或1来表示,即1024种情况可以用0000000000~1111111111之间的所有二进制数来表示,
这样问题就又转化成如何产生这1024个十进制数,很简单,编一个函数,对于1~1024之间任意一个十进制数通过除二取余就可得到。现在这个问题就迎刃而解喽。
以下是我写的代码。
#include<stdio.h>
#include<stdlib.h>
void zhuanhua(int i,int a[10]){
int n=8;
int k=i;
a[9]=k%2;
k=k/2;
while(k){
a[n]=k%2;
k=k/2;
n--;
}
}
int main(){
int a[10]={0},b[10]={0};
int i=0,l;
float n,k;
printf("please input the value:");
scanf("%f",&n);
while(i<=1023){
zhuanhua(i,a);
for(l=0;l<=9;l++)
{
if(!(l%2)) b[l]=a[l]*1.0;
else if(a[l]==0) b[l]=-1.0;
else b[l]=1.0;
}
k=b[0]*b[1]*1+b[2]*b[3]*3+b[4]*b[5]*9+b[6]*b[7]*27+b[8]*b[9]*81;
if(k==n) {printf("%d*%d*1+%d*%d*3+%d*%d*9+%d*%d*27+%d*%d*81",b[0],b[1],b[2],b[3],b[4],b[5],b[6],b[7],b[8],b[9]);
break;
}
    i++;
}
system("pause");
}
   此外,在这期间我还浏览了网上高人的算法。他们的思路用我们行内话就是递归。采用递归的确是省事不少,但关键是不好想,所以高人就是高人,高中自有高中手。在这稍微为这个思路增色一下。
这里利用1,4,13,40,121划分了四个区间,至于这五个数字从何而来,显然是前n项的和,(数列1,3,9,27,81),(1,4)区间里必然会有数字3,(4,13)里必然会有9,以此类推。所以每当
给定一个数,就先锁定范围,让后再细分,直到再不能细分为止。这个划分很有讲究,这样会使差值落在之前的一个区具体的间上,以此类推。可上网查看具体步骤和代码。
   不最后,大功告成啦。
   后记:宁做凤尾,不做鸡头。
搜索更多相关主题的帖子: 小菜 如何 
2014-03-22 20:18



参与讨论请移步原网站贴子:https://bbs.bccn.net/thread-428982-1-1.html




关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.450768 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved