總和等於給定數量

Question

我試圖解決以下問題：

什麼是總結所需要factoriais的最小數量等於一個給定數一個？ （1≤一個≤10^5）

實施例：

輸入：10，輸出：3（!!! 10 = 3 + 2 + 2）

輸入：25，輸出：2（！25 = 4 + 1！）

我的代碼：

#include<bits/stdc++.h> 

using namespace std; 

int a; 

int rec(int vet){ 

    int count = 0; 

    a = a - vet; 
     if(a >= vet){ 
      count++; 
      rec(vet); 
     } 
    count++; 
    return count; 
} 

int main(){ 

    int vet[8] = {1}, count = 0; 

    cin >> a; 

    for(int i = 2; i <= 8; i++){ 
     vet[i-1] = vet[i-2]*i; 
    } 

    for(int i = 7; i >= 0; i--){ 
     if(a < vet[i]){ 
      continue; 
     } 

     count += rec(vet[i]); 
    } 

    cout << count << endl; 
} 

我的邏輯：

1°：一個 max爲等於100000，所以我們必須 最大fatorial比較是8;！

2°：我把等於或最小的factioral設置爲a, 從它減去階乘並計算++;如果在減法之後，我的因子仍然大於 a，我會以遞歸方式執行相同的步驟。

此代碼傳遞給基礎案例，但我得到了錯誤的答案。我無法找到它沒有通過的情況，所以我在這裏。

你能找到我錯在哪裏嗎？或者如果我的解決方案不好，我應該嘗試另一種方法。

感謝您的幫助！

Answer 1

正如我在評論中提到的那樣，問題在於rec函數。由於rec是本地的，所以計數沒有被正確地遞增。

一個簡單的解決辦法是更換錄製功能如下

int rec(int vec) { 
    int count = a/vec; 
    a = a % vec; 
    return count; 
} 

編輯：對於一個失敗的情況下，嘗試18.解決方案將是3，但你會得到2 我想你能弄清楚這個邏輯如何工作。如果沒有，你可以做一個循環。

Answer 2

該問題很容易通過遞歸方法解決。

這裏檢查代碼：

#include <iostream> 

using namespace std; 

int factorial(int n) { 
     return n<=1 ? 1 : n * factorial(n-1); 
    } 


int MinFact(int number) 
{ 
      static int num_of_facts; 
      int a = 1; 
      if (number) 
      { 
         while(factorial(a+1)<=number)a++; 
         cout << a << "!" << endl; 
         num_of_facts++; 
         MinFact((number-factorial(a))); 
      } 
      return num_of_facts; 
} 


int main() 
{ 
      int num; 
      cout << "Enter number" << endl; 
      cin >> num; 
      num = MinFact(num); 
      cout << "Number of factorials: " << num; 
      return 0; 
}