資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究在 C++ 中查詢具有給定位數和數字和的最大數
在這個問題中，我們得到了兩個整數值，N 表示數字的位數，sum 表示數字的數字和。我們的任務是 *查詢具有給定位數和數字和的最大數*。
讓我們舉一個例子來理解這個問題，
Input : N = 3, sum = 15 Output : 960
解決方案方法
解決該問題的一種簡單方法是從最大到最小遍歷所有 N 位數字。查詢數字和數字，如果它等於 sum，則返回該數字。
示例
程式說明我們解決方案的工作原理
#include <iostream>
using namespace std;
int digitSum(int n){
int sum = 0;
while(n){
sum += n%10;
n = n/10;
}
return sum;
}
int findLargestNumWithSum(int N, int sum){
if (sum == 0){
if(N == 1)
return -1;
else
return -1;
}
if (sum > 9*N){
return -1;
}
int num = 1;
for(int i = 0; i < N; i++)
num *= 10;
while(1){
if(digitSum(num) == sum){
return num;
}
num -- ;
if(num == 0)
return -1;
}
}
int main(){
int sum = 25, N = 3;
cout<<"The largest "<<N<<" digit number with sum "<<sum<<" is "<< findLargestNumWithSum(N, sum);
return 0;
}輸出
The largest 3 digit number with sum 25 is 997
解決該問題的另一種方法是使用貪心演算法。我們將從 MSB 開始，從 sum 中放置儘可能大的數字，並從 sum 中減去它。
我們將執行此步驟 N 次，我們將得到所需的數字。因此，如果 sum 大於 9，則將 9 放置到當前數字，如果它小於 9，則將 sum 放置到當前數字。執行此過程，從 MSB 到 LSB 為所有數字放置數字。
示例
程式說明我們解決方案的工作原理
#include <iostream>
using namespace std;
int findLargestNumWithSum(int N, int sum){
if (sum == 0){
if(N == 1)
return -1;
else
return -1;
}
if (sum > 9*N){
return -1;
}
int num = 0;
for (int i = 0; i < N; i++){
if (sum >= 9){
num += 9;
sum -= 9;
if(i < (N - 1)){
num *= 10;
}
}
else{
num += sum;
sum = 0;
if( i < (N - 1))
num *= 10;
}
}
return num;
}
int main(){
int sum = 25,
N = 3;
cout<<"The largest "<<N<<" digit number with sum "<<sum<<" is "<<findLargestNumWithSum(N, sum);
return 0;
}輸出
The largest 3 digit number with sum 25 is 997
更新於： 2022-01-28
1K+ 瀏覽量
廣告