Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में N को योग के रूप में व्यक्त करने के लिए आवश्यक न्यूनतम पालिंड्रोम की संख्या

समस्या कथन

एक संख्या N दी गई है, हमें N को पालिंड्रोम के योग के रूप में व्यक्त करने के लिए आवश्यक न्यूनतम पालिंड्रोम की संख्या ढूंढनी है।

यदि N=15, तो 2 पालिंड्रोम आवश्यक हैं: 8 और 7।

एल्गोरिदम

1. N तक के सभी पालिंड्रोम को सॉर्टेड तरीके से उत्पन्न करें
2. सबसे छोटे सबसेट का आकार ढूंढें जिसका योग N हो

C++ उदाहरण

#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, 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
  1. - C++ में N को 25 से विभाज्य बनाने के लिए दिए गए मूव्स की न्यूनतम संख्या

    समस्या कथन अग्रणी शून्य के बिना एक संख्या N दी गई है। N को 25 से विभाज्य बनाने के लिए आवश्यक न्यूनतम मूव्स की संख्या ढूंढें। प्रत्येक मूव में, कोई भी दो आसन्न अंकों को स्वैप कर सकता है और यह सुनिश्चित करना होगा कि किसी भी समय संख्या में कोई अग्रणी शून्य न हो। यदि N को 25 से विभाज्य बनाना संभव नहीं ह

  1. - C++ में किसी संख्या के गुणनखंडों का न्यूनतम योग ढूंढना

    यहां हम देखेंगे कि किसी दी गई संख्या के गुणनखंडों का न्यूनतम योग कैसे प्राप्त करें। मान लीजिए एक संख्या 12 है। हम इसे अलग-अलग तरीकों से गुणनखंडित कर सकते हैं: 12 = 12 × 1 (12 + 1 = 13) 12 = 2 × 6 (2 + 6 = 8) 12 = 3 × 4 (3 + 4 = 7) 12 = 2 × 2 × 3 (2 + 2 + 3 = 7) न्यूनतम योग 7 है। हम

  1. - C++ में न्यूनतम पृष्ठों का आवंटन

    न्यूनतम पृष्ठों का आवंटन एक प्रोग्रामिंग समस्या है। आइए इस समस्या पर विस्तार से चर्चा करते हैं और देखते हैं कि इसका समाधान क्या हो सकता है। कथन आपको n विभिन्न पुस्तकों के पृष्ठों की संख्या दी गई है। साथ ही, m छात्र हैं जिन्हें पुस्तकें आवंटित की जानी हैं। पुस्तकें पृष्ठों की संख्या के आरोही क्रम में