projecteuler No.145 How many reversible numbers are there below one-billion?

发布时间:2016-12-11 4:55:41 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"projecteuler No.145 How many reversible numbers are there below one-billion?",主要涉及到projecteuler No.145 How many reversible numbers are there below one-billion?方面的内容,对于projecteuler No.145 How many reversible numbers are there below one-billion?感兴趣的同学可以参考一下。

原文题目链接: http://projecteuler.net/problem=145 翻译题目链接: http://pe.spiritzhang.com/index.php/2011-05-11-09-44-54/147-14510 通过人数:8630 题目分析: 这道题其实情况数不多,可以对10^9进行枚举,大概几分钟就可以做出来。 但其实也有不需要计算机的纯数学解法。我附在解法二中。 解法一:大量的枚举 解题过程(代码仅供参考,因为偷懒,代码风格什么的实在不好意思...): if (i % 10 == 0) continue;依题意,跳过末尾为0的数。其中,i为从1到1000000000循环的数。 int k = i; while(k) { a[la] = k % 10; la++; k /= 10; }将i转存到数组a[]中。la为a的长度,初始为0; for (int j = 0; j < la; j++) { b[j] += a[j] + a[la - 1 - j]; if (b[j] >= 10) { b[j]%=10; b[j+1]++; } } if (b[la]) lb = la + 1; else lb = la;计算a[]与a[]的逆序的和并存入b[]中。检查进位判断b[]的长度lb。 for (int j = 0; j < lb; j++) { if (b[j] % 2 == 0) goto next; } ans++;若计算出来的b[]每一位都是奇数,计数器加1。 最后输出ans结果为608720。 用时大概是几分钟的样子,没有准确计时。 解法二:纯数学解法 解题过程: 一、首先证明,9位数中没有满足条件的reversible numbers 反证:若有,设为abcdefghi 考察abcdefghi+ighfedcba从右数第5位。 若第4位未发生进位,则该位为2e%10,不为奇数,故第4位发生进位。 所以,第6位也发生进位,(c+h)%10为偶数。 所以第2位也发生进位。 所以,第8位也发生进位,(a+i)%10为偶数。 所以这个和的最后一位为偶数,矛盾。 故9位数中没有满足条件的reversible numbers。 【其实到现在从1~10^8进行搜索是最明智的选择,3s之内可以搞定。但谁让我们是在说纯数学做法呢~O(∩_∩)O~】 同理可证5位数和1位数中没有满足条件的reversible numbers(对4k+1位数均适用) 二、其次,我们来求有多少8位数是满足条件的reversible numbers 从现在开始,我们定义几个数对集,这几个数对集的元素个数比较好求,已标在集合定义的后面。 A1={(x,y)|(x+y)%2=1且x+y<10且x,y为1~9的整数};   |A1| = 20 B1={(x,y)|(x+y)%2=0且x+y<10且x,y为1~9的整数};   |B1| = 16 C1={(x,y)|(x+y)%2=1且x+y>=10且x,y为1~9的整数}; |C1| = 20 D1={(x,y)|(x+y)%2=0且x+y>=10且x,y为1~9的整数}; |D1| = 25 A0={(x,y)|(x+y)%2=1且x+y<10且x,y为0~9的整数};   |A0| = 30 B0={(x,y)|(x+y)%2=0且x+y<10且x,y为0~9的整数};   |B0| = 25 设数abcdefgh是一个8位reversible number。 记和为abcdefgh+hgfedcba case1 (a,h)∈A1 考察和的从右数第2位和第8位,有(b,g)∈A0 同理,(c,f),(d,e)均属于A0。 而显然,满足上述条件的8位数是reversible number。 故这个case的答案种数有20*30^3=540000 case2 (a,h)∉A1,则显然(a,h)∈C1 考察和的从右数第2位,(b+g)%2=0.考察和的从右数第9位,有b+g<10。 故(b,g)∈B0. 考察和的从右数第3位和第7位,有(c,f)∈C1 考察和的从右数第4位和第6位,有(d,e)∈B0 考察和的从右数第5位,发现时偶数。 故这个case下没有reversible number。 综上所述,有540000个8位数是reversible numbers 三、接下来,我们来求有多少7位数是满足条件的reversible numbers 设数abcdefg是一个7位reversible number。 记和为abcdefg+gfedcba 考察和的从右数4位,若其为奇数,有:c+e>10 考察和的从右数6位,有(b+f)%10%2=0 考察和的从右数2位,有a+c>10. 进一步考察和的最右位,有(a,c)∈C1 进一步考察和的从右数7位,有(b,f)∈B0 进一步考察和的从右数3位,有(c,e)∈C1 考察和的从右数5位,有d∈{0,1,2,3,4} 而显然,满足上述条件的7位数是reversible number。 故共有7位reversible number 20*20*25*5 = 50000个 四、然后,我们来求有多少6位数是满足条件的reversible numbers 而这段分析,其实是完全类似于对8位数的分析的,在此就不写了。一共有20*30*30=18000个。 五、最后,我们来求有多少4位数是满足条件的reversible numbers 而这段分析,其实也是完全类似于对8位数的分析的,在此就不写了。一共有20*30=600个。 于是汇总上题干中的信息(不超过1000的reversible numbers有120个),答案为120+600+18000+540000=608720 以上只是我做题时的解法。 如果有更好的解法、更好的思路,欢迎评论讨论~O(∩_∩)O~

上一篇:计算机核心期刊新排名(八大学报)
下一篇:Netty源码解读(四)Netty与Reactor模式

相关文章

相关评论