对给定的整数进行分解与重组,整合为满足某些特定条件的数组,是一项具有挑战性的设计,也是一类非常有趣的智力游戏;
本节探索“双和3元2组”与“和积3元3组”两个案例,注意分解的实施与重组条件“双和”、“和积”的实现;
把给定偶数2n分解为6个互不相等的正整数a、b、c、d、e、f,然后把这6个数分成(a、b、c)与(d、e、f)两个3元组,若这两个3元组具有和相等且倒数和也相等的双和相等特性:
a+b+c=d+e+f
1/a+1/b+1/c=1/d+1/e+1/f
则把3元组(a、b、c)与(d、e、f)(约定a< b< c,d< e< f,a< d)称为基于n的双和3元2组;
例如,对于n=26,存在基于26的双和3元2组(4、10、12)和(5、6、15):
4+10+12=5+6+15=26
1/4+1/10+1/12=1/5+1/6+1/15=13/30
输入正整数n(n<=100),搜索基于n的所有双和3元2组,若没有探索到相应的双和3元2组,则输出“无解”;
1.说明:
因6个不同正整数之和至少为21,即整数n>=11;
(1)、枚举循环设置;
设置a,b与d,e枚举循环,注意到a+b+c=n,且a< b< c,因而a,b循环取值为:
a:1~(n-3)/3,因为b比a至少大1,c比a至少大2,a的值最多为(n-3)/3;
b:a+1~(n-a-1)/2,因为c比b至少大1,b的值最多为(n-a-1)/2;
c=n-a-b,以确保a+b+c=n;
设置d,e循环基本同上,注意到d>a,因而d起点为a+1;
(2)、检验倒数和相等;
把比较倒数和相等1/a+1/b+1/c=1/d+1/e+1/f 转化为比较整式:
- d*e*f*(b*c+c*a+a*b)=a*b*c*(e*f+f*d+d*e)
若等式不成立,即倒数和不相等,则返回;
(3)、省略相同整数的检测;
注意到两个3元组中若部分相同部分不同,不能有和相等且倒数和也相等,因而可省略排除以上6个正整数中是否存在相等的检测;
若比较整式成立,打印输出和为n的双和3元2组,并用x统计解的个数;
2.程序设计:
3.程序运行示例及其注意事项:
输入n=26,即得唯一一个双和3元2组如上面叙述所示,输入任何小于26的整数n均无解,可见存在双和3元2组的n最小值为26;
注意:由循环设置可知枚举复杂度为O(n^4),显然不适宜对较大整数n的双和3元2组搜索;
设n为正整数,试把整数3*n分解为9个互不相同的正整数a、b、c、d、e、f、g、h、i,然后把这9个正整数分成(a,b,c)、(d,e,f)与(g,h,i)共3个3元组,若这3个3元组具有和相等且积相等的两个相等特性:
- a+b+c=d+e+f=g+h+i=n
- a*b*c=d*e*f=g*h*i
则把(a,b,c)、(d,e,f)与(g,h,i)(约定a< b< c,d< e< f,g< h< i,a< d< g)称为一个基于n的和积3元3组;
例如,给定n=45,探索到基于45的和积3元3组(4,20,21)、(5,12,28)和(7,8,30):
4+20+21=5+12+28=7+8+30=45
4*20*21=5*12*28=7*8*30=1680
输入正整数n(n<=100),搜索基于n的所有和积3元3组,若没有探索到相应的和积3元3组,则输出“无解”;
1.说明:
因为9个不同正整数之和至少为45,故可知正整数n>14;
(1)、设置枚举循环;
注意到a+b+c=n,且a< b< c,因而a,b循环取值为:
a:1~(n-3)/3,因为b比a至少大1,c比a至少大2,即a至多为(n-3)/3;
b:a+1~(n-a-1)/2,因为c比b至少大1,即b至多为(n-a-1)/2;
c=n-a-b,以确保a< b< c且a+b+c=n;
设置d,e循环与g,h循环基本同上,只是注意到d>a,因而d起点为a+1;g>d,因而g起点为d+1;
(2)、检测和积相等;
在设置的枚举循环中,确保了3个3元组和相等;
若a*b*c=d*e*f=g*h*i,即积也相等,满足和积相等条件,搜索到基于n的一组和积3元3组,用x统计组数;
(3)、省略相同整数的检测;
注意到两个和相等的3元组中,若等号两边有部分数相同部分数不同,不可能有积相等(证略);
因而可省略排除以上9个正整数中是否存在相同整数的检测,即在检测积相等时已排除出现整数相同的可能;
3.程序设计:
3.程序运行示例及其注意事项:
请运行程序,探索存在基于n的和积3元3组的整数n至少为多大?