本文主要是介绍有一个正整数N可以分解成若干个正整数之和,问如何分解能使这些数的乘积最大?,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
这个题若无整数条件限制,其实答案是全部分解为e(2.71828的那个e)
拿到此题,想起了天平称小球问题:n 个球中有一个是轻的,试问:怎样用一个没有砝码的天平,用最少的次数找出是哪个球,请算出最少次数。这个题的答案是:当 log3(n)为整数时,最少称log3(n)次,否则,最少称( [log3(n)]+1 )次。
于是乎,猜测本题应该是将N尽量分解为若干个3,直到不能分解出3,再做出适当的调整。
就本题而言,易知,N必为 3n型、3n+1型、3n+2型中的一种(由数论的基本知识知:一个数 mod q,所得数值必在0到q - 1之间),N为3n型数据时,直接全部分解为3;N为 3n+1型数据时,最后会出现4,对4不做分解;N为3n+2型数据时,最后会出现5,将5分解为3和2。而N能分解成[N/3]个3。
这个问题的证明如下:
https://www.zhihu.com/question/30071017/answer/257494547
这个问题终于能和学过的高数知识和不等式知识联系起来了
代码如下:
#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;double f(int N); //分解N的函数 int main()
{int N;while (cin >> N && N){printf ("%f\n",f(N));}return 0;
}double f(int N) //易知,N必为 3n型、3n+1型、3n+2型中的一种(由数论的基本知识知:一个数 mod q,所得数值必在0到q - 1之间)
{int k = N / 3; if (N == 1)return 1; if (N % 3 == 0) // 如果N为 3n型 数据 return pow(3, k); if (N % 3 == 1) // 如果N为 3n+1型 数据return 4.0 * pow(3, k - 1);else // 如果N为 3n+2型 数据return 2.0 * pow(3, k);
}
这篇关于有一个正整数N可以分解成若干个正整数之和,问如何分解能使这些数的乘积最大?的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!