累进可除数
首个位非零而且由它首n个位组成的数是n的倍数
累进可除数(英:Polydivisible number)是有以下特质的整数:首个位非零,而且由它首n个位组成的数是n的倍数。
简介
例如345654:
1|3
2|34
3|345
4|3456
而123456就非累进可除数,因为1234不是4的倍数。
累进可除数可以在不同的进位制中定义。本条目仅谈论十进制中的情况。
背景
累进可除数是趣味数学上的一道名题的一般化:
用1至9排列成一个数,使其首2个位能被2除尽,首3个位能被3除尽,如此类推,整个数是9的倍数。
虽然9位的累进可除数有2492个,但唯一一个包含1至9的数字而不重覆的只有一个,是381 654 729。
C语言实例
求九位累进可除数。所谓九位累进可除数就是这样一个数:这个数用到1到9这九个数字组成,每个数字刚好只出现一次。这九个位数的前两位能被2整除,前三位能被3整除......前N位能被N整除,整个九位数能被9整除。
*问题分析与算法设计
问题本身可以简化为一个穷举问题:只要穷举每位数字的各种可能取值,按照题目的要求对穷举的结果进行判断就一定可以得到正确的结果。
问题中给出了“累进可除”这一条件,就使得我们可以在穷举法中加入条件判断。在穷举的过程中,当确定部分位的值后,马上就判断产生的该部分是否符合“累进可除”条件,若符合,则继续穷举下一位数字;否则刚刚产生的那一位数字就是错误的。这样将条件判断引入到穷举法之中,可以尽可能早的发现矛盾,尽早地放弃不必要穷举的值,从而提高程序的执行效率。
为了达到早期发现矛盾的目的,不能采用多重循环的方法实行穷举,那样编出的程序质量较差。程序中使用的算法不再是穷举法,而是回朔法。
求N位累进可除数。用1到9这九个数字组成一个N(3< =N< =9)位数,位数字的组成不限,使得该N位数的前两位能被2整除,前3位能被3整除,......,前N位能被N整除。求满足条件的N位数。
参考资料
最新修订时间:2024-06-19 18:26
目录
概述
简介
C语言实例
参考资料