数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
安卓
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时装研究
法律研究用 C++ 表示 N 为和所需的回文数最小数量。
问题陈述
给定一个数字 N，我们必须找出表示 N 为它们的和所需的最小回文数数量
如果 N = 15，则需要 2 个回文数，即 8 和 7。
算法
1. Generate all the palindromes up to N in a sorted fashion 2. Find the size of the smallest subset such that its sum is N
示例
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;
vector<vector<long long>> table;
int createPalindrome(int input, bool isOdd){
int n = input;
int palindrome = input;
if (isOdd)
n /= 10;
while (n > 0) {
palindrome = palindrome * 10 + (n % 10);
n /= 10;
}
return palindrome;
}
vector<int>generatePalindromes(int n){
vector<int> palindromes;
int number;
for (int j = 0; j < 2; j++) {
int i = 1;
while ((number = createPalindrome(i++, j)) <= n)
palindromes.push_back(number);
}
return palindromes;
}
long long minSubsetSize(vector<int>& vec, int i, int j, int n){
if (n == 0)
return 0;
if (i > j || vec[i] > n)
return INT_MAX;
if (table[i][n])
return table[i][n];
table[i][n] = min(1 + minSubsetSize(vec, i + 1, j, n - vec[i]), minSubsetSize(vec, i + 1, j, n));
return table[i][n];
}
int requiredPalindromes(int n){
vector<int> palindromes = generatePalindromes(n);
sort(palindromes.begin(), palindromes.end());
table = vector<vector<long long>>(palindromes.size(),
vector<long long>(n + 1, 0));
return minSubsetSize(palindromes, 0, palindromes.size() - 1, n);
}
int main(){
int n = 15;
cout << "Minimum required palindromes = " <<
requiredPalindromes(n) << endl;
return 0;
}输出
编译并执行以上程序时。它将生成以下输出 −
Minimum required palindromes = 2
更新于：31-Oct-2019
已查看 154 次
广告