c – 找到最小整数,其数字平方和加到给定数字

发布时间：2020-12-16 10:04:37 所属栏目：百科来源：网络整理

导读：例：输入：|输出： 5 – 12(1 ^ 2 2 ^ 2 = 5) 500 – 18888999(1 ^ 2 8 ^ 2 8 ^ 2 8 ^ 2 9 ^ 2 9 ^ 2 9 ^ 2 = 500) 我写了一个非常简单的暴力解决方案,但它有很大的性能问题： #include iostreamusing namespace std;int main() { int n; bool found = true

例：

输入：|输出：

> 5 – > 12(1 ^ 2 2 ^ 2 = 5)
> 500 – > 18888999(1 ^ 2 8 ^ 2 8 ^ 2 8 ^ 2 9 ^ 2 9 ^ 2 9 ^ 2 = 500)

我写了一个非常简单的暴力解决方案,但它有很大的性能问题：

#include <iostream>
using namespace std;

int main() {
 int n;
 bool found = true;
 unsigned long int sum = 0;

 cin >> n;
 int i = 0;
 while (found) {
     ++i;
     if (n == 0) { //The code below doesn't work if n = 0,so we assign value to sum right away (in case n = 0)
         sum = 0;
         break;
     }
     int j = i;
     while (j != 0) { //After each iteration,j's last digit gets stripped away (j /= 10),so we want to stop right when j becomes 0
         sum += (j % 10) * (j % 10); //After each iteration,sum gets increased by *(last digit of j)^2*. (j % 10) gets the last digit of j
         j /= 10;
     }
     if (sum == n) { //If we meet our problem's requirements,so that sum of j's each digit squared is equal to the given number n,loop breaks and we get our result
        break;
     }
     sum = 0; //Otherwise,sum gets nullified and the loops starts over
 }

 cout << i;

 return 0;
 }

我正在寻找一个快速解决问题的方法.

解决方法

使用动态编程.如果我们知道最优解的第一个数字,那么其余的将是剩余总和的最优解.因此,我们可以猜测第一个数字并对较小的目标使用缓存计算以获得最佳数据.

def digitsum(n):
    best = [0]
    for i in range(1,n+1):
        best.append(min(int(str(d) + str(best[i - d**2]).strip('0'))
                        for d in range(1,10)
                        if i >= d**2))
    return best[n]

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!