توليد أرقام N أرقام متسلسلة بمجموع أرقام فردية (بدون إصداقية)

Question

أنا أتطلع إلى إنشاء جميع القيم الممكنة لرقم N رقم N، بالترتيب التالي، حيث تملي التسلسل بمجموع الأرقام الفردية.

على سبيل المثال، مع n = 3:

111     sum = 3
112     sum = 4
121
211
122     sum = 5
212
221
113
131
311
114     sum = 6
141
411
:::
999     sum = 27

النظام ضمن مجموعة المجموعات غير مهم.

أي مساعدة، ستكون الأفكار موضع تقدير

Answer 1

يمكنك دائما قم بتشغيل مشكلة متكررة في أحد التكرار إذا حافظت على كومة من البيانات المهمة - فهذا إذا كان السبب في تجنب العودية هو أن اللغة لا تدعمها.

ولكن، إذا كانت اللغة هل دعمها، ثم الحلول العودية هي أناقة أكثر بكثير.

السبب الآخر الوحيد الذي يمكنني التفكير فيه في تجنب العودية عمق مكدس محدود. في هذه الحالة، سيقوم بتحويل تكراري لحل متكرر في تخفيف المشكلة من خلال عدم طلب مساحة مكدس.

ولكن عليك أن تفهم أن عمق المكدس لمعالجة الأرقام N ينمو فقط نسبة إلى السجل₁₀ن. بمعنى آخر، يمكنك فقط الحصول على إطار مكدس إضافي لكل رقم (10 إطارات مكدس فقط للتعامل مع مجموعة كاملة من الأعداد الصحيحة 32 بت).

جانبا: بحلول الوقت الذي تحصل فيه إلى هذه النقطة، ستكون خوارزمية ستستغرق وقتا طويلا لتشغيل، ستكون إطارات المكدس أقل مشاكلك :-)

إليك محلول ثعبان متكرر:

def recur (numdigits,sum,pref="",prefsum=0):
    if numdigits == 0:
        if prefsum == sum:
            print "%s, sum=%d"%(pref,prefsum)
    else:
        for i in range (1,10):
            recur (numdigits-1,sum,"%s%d"%(pref,i),prefsum+i)

def do (n):
    for i in range (1,n*9+1):
        recur (n,i)

do (2)
do (3)

ما الناتج (لمدة 2 و 3):

11, sum=2          111, sum=3
12, sum=3          112, sum=4
21, sum=3          121, sum=4
13, sum=4          211, sum=4
22, sum=4          113, sum=5
31, sum=4          122, sum=5
14, sum=5          131, sum=5
23, sum=5          212, sum=5
32, sum=5          221, sum=5
41, sum=5          311, sum=5
15, sum=6          114, sum=6
 :    :             :     :
89, sum=17         989, sum=26
98, sum=17         998, sum=26
99, sum=18         999, sum=27

ضع في اعتبارك أن الحل لا يزال من الممكن تحسينه إلى حد ما - تركته في شكله الأولي لإظهار مدى أن تكون العودية الأنيقة. يتبع حل تكريري خالص، لكنني ما زلت أفضل فترة التكريس.

قم بتشغيل البرنامج التالي واستخدامه sort و awk ضمن UNIX للحصول على الترتيب المطلوب. علي سبيل المثال:

go | sort | awk '{print $2}'

لاحظ أن هذا يستخدم أدوات خارجية للقيام بالفرز ولكن يمكنك بسهولة الفرز داخل رمز C (سمح الذاكرة).

#include <stdio.h>

int main (void) {
    int i, sum, carry, size;
    int *pDigit;

    // Choose your desired size.

    size = 2;

    // Allocate and initialise digits.

    if ((pDigit = malloc (size * sizeof (int))) == NULL) {
        fprintf (stderr, "No memory\n");
        return 1;
    )

    for (i = 0; i < size; i++)
        pDigit[i] = 1;

    // Loop until overflow.

    carry = 0;
    while (carry != 1) {
        // Work out sum, then output it with number.
        // Line is sssssssssssssssssss ddddd
        //   where sss...sss is the fixed-width sum, zero padded on left (for sort)
        //   and ddd...ddd is the actual number.

        sum = 0;
        for (i = 0; i < size; i++)
            sum += pDigit[i];

        printf ("%020d ", sum);
        for (i = 0; i < size; i++)
            printf ("%d", pDigit[i]);
        printf ("\n");

        // Advance to next number.

        carry = 1;
        for (i = 0; i < size; i++) {
            pDigit[size-i-1] = pDigit[size-i-1] + carry;
            if (pDigit[size-i-1] == 10)
                pDigit[size-i-1] = 1;
            else
                carry = 0;
        }
    }

    return 0;
}

Answer 2

هل تستطيع استعمال STD :: next_permulation.?

تحاول الدالة next_permutation () تحويل النطاق المحدد للعناصر [البداية، النهاية) إلى التقليب الأساسي المعجم التالي من العناصر. إذا نجحت، فإنه يعود صحيحا، وإلا فإنه يعود خطأ.

إذا تم توفير كائن وظيفة ضعيفة ضعيفة بشكل ضعيف، يتم استخدامه بدلا من ذلك في <المشغل عند مقارنة العناصر.

انظر الى هذا: السابق حتى الإجابة

Answer 3

إذا لم يكن الأمر فلا يهم النمط الذي تستخدمه طالما يوجد نمط (ليس واضحا تماما من منشورك ما إذا كان لديك نمط معين في الاعتبار)، ثم نبدأ N = 3، 111 وزيادة حتى تصل 999.

بالمناسبة، مصطلح ما تطلبه ليس بالضبط "التباديل".

Answer 4

يمكنك محاولة تقليل مشكلتك إلى دلاءين:

اثنين من الانقسامات دلو بسيطة: ابدأ بكل ناقص واحد في دلو A وواحد في دلو B، ثم ضع واحدة من A إلى B حتى يحتوي على واحد فقط.

ثلاثة انقسامات دلو ثم فقط: البدء بكل ناقص اثنين في دلو واحد وواحد في كل من B و C. تقليل أ