История изменений

Исправление dissident, 25.11.13 12:41 (текущая версия) :

Да, я уже заметил ошибку. Вот так все верно:

#include <list>
#include <algorithm>
#include <cstdio>
using namespace std;

static long long banknotes[] = { 1, // 2^0
                                 2, // 2^1
                                 4, // 2^2
                                 8, // 2^3
                                 16, // 2^4
                                 32, // 2^5
                                 64, // 2^6
                                 128, // 2^7
                                 256, // 2^8
                                 512 // 2^9
                               };

static int numberOfBanknotes = 10;

static long long numberOfSolutions = 0;

void printBanknote(long long banknote)
{
    printf("%lld + ", banknote);
}

void printSolution(list<int> solution)
{
    printf("Solution: ");
    for_each(solution.begin(), solution.end(), printBanknote);
    putchar('\n');
}

void exchange(long long banknote, long long prevBanknote)
{
    if (banknote == 0)
    {
        numberOfSolutions++;
        if (numberOfSolutions % 1000000 == 0)
            printf("Solution %lld\n", numberOfSolutions);
    }

    if (banknote <= 0)
        return;

    for (int i = numberOfBanknotes-1; i >= 0; i--)
    {
        if (banknotes[i] > prevBanknote)
            continue;
        exchange(banknote - banknotes[i], banknotes[i]);
    }
}

int main()
{
    exchange(1024, 1024);
    printf("Number of solutions %lld\n", numberOfSolutions);
}

Ответ мне выдало:

Number of solutions 2320518947

Правда это без повторений, т.е. 256+512+256=256+256+512. Если с повторениями, то я, почитав про динамическое программирование, делал бы так:

Одна одномерная таблица F[1024].

F[1] = 1 (т.к. банкноту достоинством 1 можно разменять один раз на себя же).
F[2] = 1,1 или 2 = 2
F[3] = 1,1,1; 2,1; 1,2
F[4] = 1 (self) + F[2] + F[3] 
F[5] = F[1] + F[3] + F[4]
F[6] = F[2] + F[4] + F[5]
F[7] = F[3] + F[5] + F[6]
F[8] = 1 (self) + f[4] + F[6] + F[7]

И так далее. Не понятно, почему у тебя двумерная таблица.

Исправление dissident, 25.11.13 12:36:

Да, я уже заметил ошибку. Вот так все верно:

#include <list>
#include <algorithm>
#include <cstdio>
using namespace std;

static long long banknotes[] = { 1, // 2^0
                                 2, // 2^1
                                 4, // 2^2
                                 8, // 2^3
                                 16, // 2^4
                                 32, // 2^5
                                 64, // 2^6
                                 128, // 2^7
                                 256, // 2^8
                                 512 // 2^9
                               };

static int numberOfBanknotes = 10;

static long long numberOfSolutions = 0;

void printBanknote(long long banknote)
{
    printf("%lld + ", banknote);
}

void printSolution(list<int> solution)
{
    printf("Solution: ");
    for_each(solution.begin(), solution.end(), printBanknote);
    putchar('\n');
}

void exchange(long long banknote, long long prevBanknote)
{
    if (banknote == 0)
    {
        numberOfSolutions++;
        if (numberOfSolutions % 1000000 == 0)
            printf("Solution %lld\n", numberOfSolutions);
    }

    if (banknote <= 0)
        return;

    for (int i = numberOfBanknotes-1; i >= 0; i--)
    {
        if (banknotes[i] > prevBanknote)
            continue;
        exchange(banknote - banknotes[i], banknotes[i]);
    }
}

int main()
{
    exchange(1024, 1024);
    printf("Number of solutions %lld\n", numberOfSolutions);
}

Ответ мне выдало:

Number of solutions 2320518947

Одна одномерная таблица F[1024].

F[1] = 1 (т.к. банкноту достоинством 1 можно разменять один раз на себя же).
F[2] = 1,1 или 2 = 2
F[4] = 1 (сам себя) + F[2] + F[1]
F[8] = 1 + F[4] + F[2] + F[1]
F[16] = 1 (сам себя) + F[8] + F[4] + F[2] + F[1]
F[32] = 1 + F[16] + F[8] + F[4] + F[2] + F[1]

И так далее. Не понятно, почему у тебя двумерная таблица.

Исправление dissident, 25.11.13 12:35:

Да, я уже заметил ошибку. Вот так все верно:

#include <list>
#include <algorithm>
#include <cstdio>
using namespace std;

static long long banknotes[] = { 1, // 2^0
                                 2, // 2^1
                                 4, // 2^2
                                 8, // 2^3
                                 16, // 2^4
                                 32, // 2^5
                                 64, // 2^6
                                 128, // 2^7
                                 256, // 2^8
                                 512 // 2^9
                               };

static int numberOfBanknotes = 10;

static long long numberOfSolutions = 0;

void printBanknote(long long banknote)
{
    printf("%lld + ", banknote);
}

void printSolution(list<int> solution)
{
    printf("Solution: ");
    for_each(solution.begin(), solution.end(), printBanknote);
    putchar('\n');
}

void exchange(long long banknote, long long prevBanknote)
{
    if (banknote == 0)
    {
        numberOfSolutions++;
        if (numberOfSolutions % 1000000 == 0)
            printf("Solution %lld\n", numberOfSolutions);
    }

    if (banknote <= 0)
        return;

    for (int i = numberOfBanknotes-1; i >= 0; i--)
    {
        if (banknotes[i] > prevBanknote)
            continue;
        exchange(banknote - banknotes[i], banknotes[i]);
    }
}

int main()
{
    exchange(1024, 1024);
    printf("Number of solutions %lld\n", numberOfSolutions);
}

Ответ мне выдало:

Number of solutions 2320518947

Одна одномерная таблица F[1024].

F[1] = 1 (т.к. банкноту достоинством 1 можно разменять один раз на себя же).
F[2] = 1,1 или 2 = 2
F[4] = 1 (сам себя) + F[2] + F[1]
F[16] = 1 (сам себя) + F[4] + F[2] + F[1]
F[32] = 1 + F[16] + F[8] + F[4] + F[2] + F[1]

И так далее. Не понятно, почему у тебя двумерная таблица.

Исходная версия dissident, 25.11.13 12:34:

Да, я уже заметил ошибку. Вот так все верно:

#include <list>
#include <algorithm>
#include <cstdio>
using namespace std;

static long long banknotes[] = { 1, // 2^0
                                 2, // 2^1
                                 4, // 2^2
                                 8, // 2^3
                                 16, // 2^4
                                 32, // 2^5
                                 64, // 2^6
                                 128, // 2^7
                                 256, // 2^8
                                 512 // 2^9
                               };

static int numberOfBanknotes = 10;

static long long numberOfSolutions = 0;

void printBanknote(long long banknote)
{
    printf("%lld + ", banknote);
}

void printSolution(list<int> solution)
{
    printf("Solution: ");
    for_each(solution.begin(), solution.end(), printBanknote);
    putchar('\n');
}

void exchange(long long banknote, long long prevBanknote)
{
    if (banknote == 0)
    {
        numberOfSolutions++;
        if (numberOfSolutions % 1000000 == 0)
            printf("Solution %lld\n", numberOfSolutions);
    }

    if (banknote <= 0)
        return;

    for (int i = numberOfBanknotes-1; i >= 0; i--)
    {
        if (banknotes[i] > prevBanknote)
            continue;
        exchange(banknote - banknotes[i], banknotes[i]);
    }
}

int main()
{
    exchange(1024, 1024);
    printf("Number of solutions %lld\n", numberOfSolutions);
}

Ответ мне выдало:

Number of solutions 2320518947

Одна одномерная таблица F[1024].

F[1] = 1 (т.к. банкноту достоинством 1 можно разменять один раз на себя же). F[2] = 1,1 или 2 = 2 F[4] = 1 (сам себя) + F[2] + F[1] F[16] = 1 (сам себя) + F[4] + F[2] + F[1] F[32] = 1 + F[16] + F[8] + F[4] + F[2] + F[1]

И так далее. Не понятно, почему у тебя двумерная таблица.