求大神解整数因子团问题!
希望可以给出C语言的源程序,或者告诉我解题思想。感激不尽啊题目描述:
整数因子团是一个有趣的智力游戏。游戏规则如下:
给定由n个连续自然数组成的序列1,…,n。
当前序列中选择一整数,它在当前序列中至少有2个因子(该整数本身可以算作一个因子,例如,整数60的所有因子是:60,30,20,15,12,10,6,5,4,3,2,1。它们构成整数60在当前序列中的因子团 )。
从当前序列中删去所选整数的所有因子。
重复步骤2和3,直到空序列或当前序列中所有数字在序列中仅有一个因子。
你在游戏中的得分是步骤2中所选择的数字的总和。
例如,当n=6时,给定的序列为1,2,3,4,5,6。
一个游戏过程是:
步骤②:选择整数5;
步骤③:从当前序列中删去整数5的所有因子5,1。
当前序列改变为:2,3,4,6。
步骤②:选择整数6;
步骤③:从当前序列中删去整数6的所有因子6,2,3。
当前序列改变为:4。游戏结束。
该游戏的得分是11。
另一个游戏过程如下:
步骤②:选择整数5;
步骤③:从当前序列中删去整数5的所有因子5,1。
当前序列改变为:2,3,4,6。
步骤②:选择整数4;
步骤③:从当前序列中删去整数4的所有因子4,2。
当前序列改变为:3,6。
步骤②:选择整数6;
步骤③:从当前序列中删去整数6的所有因子6,3。
当前序列改变为空序列。游戏结束。
该游戏的得分是15。
从上面的例子不难看出,游戏的步骤2所选数字的次序对游戏的得分有很大影响。应该如何选择才能使游戏获得最大得分?2≤n≤120。如n=6时的解为15;n=15时的解为81;n=30时的解为301;n=50时的解为808;n=65的解为1328。