首页 › 题库 › C/C++编程考级 › C/C++编程三级 › 简答题
简答题 偏难
#7534

构造性证明 关于数学定理证明,也有高下之分。最暴力的证明方法是“构造性证明”,即当需要证明某种解存在时,直接把解构造出来,而不是仅通过推理证明解之存在。 下面有…

构造性证明

关于数学定理证明,也有高下之分。最暴力的证明方法是“构造性证明”,即当需要证明某种解存在时,直接把解构造出来,而不是仅通过推理证明解之存在。

下面有一个定理:

设 ai(i=1, … , 5)均为正实数。则一定存在 4 个互不相同的下标 i、j、k、l,使得 |ai / aj - ak / al| < 1/2。

作为程序员,就请你编写程序构造出正确的下标,验证这个结论。

时间限制:1000

内存限制:65536

输入

输入在一行中顺序给出 5 个正实数。为保证计算中不产生浮点溢出,我们令输入的数字在 [10-10, 1010] 区间内,且小数点后不超过 10 位小数。

输出

在一行中首先输出使得定理结论成立的下标有多少套,随后输出最小的一套下标。数字间以 1 个空格分隔,行首尾不得有多余空格。 注:所谓下标集 {i1, …, i4} 小于下标集 {j1, …, j4},是指存在 1 ≤ k ≤ 4 使得 il=jl 对所有 l < k 成立,且 ik < jk。

样例输入

3.12 5.27 0.0007 9825.4413 10

样例输出

18 1 4 3 2

提示

样例解释: 易验证 |a1/a4-a3/a2|=|3.12/9825.4413 - 0.0007/5.27| < 1/2。满足条件的解有 18 个,例如 5、4、3、2 就是另一套解。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;algorithm&gt; #include &lt;cmath&gt; #include &lt;iomanip&gt; using namespace std; const double EPS = 1e-9; // 比较两个双精度浮点数是否相等(考虑精度误差) bool doubleEqual(double a, double b) {     return fabs(a - b) &lt; EPS; } int main() {     vector&lt;double&gt; nums(5);     for (int i = 0; i &lt; 5; ++i) {         cin &gt;&gt; nums[i];     }     int count = 0;     vector&lt;int&gt; result(4);     // 四重循环遍历所有可能的四个下标组合     for (int i = 0; i &lt; 5; ++i) {         for (int j = 0; j &lt; 5; ++j) {             if (i == j) continue;             for (int k = 0; k &lt; 5; ++k) {                 if (k == i || k == j) continue;                 for (int l = 0; l &lt; 5; ++l) {                     if (l == i || l == j || l == k) continue;                     double val = fabs(nums[i] / nums[j] - nums[k] / nums[l]);                     if (val &lt; 0.5) {                         count++;                         if (count == 1) {                             result = {i + 1, j + 1, k + 1, l + 1};                         }                     }                 }             }         }     }     cout &lt;&lt; count &lt;&lt; " ";     for (int idx : result) {         cout &lt;&lt; idx &lt;&lt; " ";     }     return 0; }</pre>
这道题暂未补解析。