Я кодирую алгоритм грубой силы при внесении изменений, и я немного застрял - PullRequest
Новая
       10

Я кодирую алгоритм грубой силы при внесении изменений, и я немного застрял

0 голосов
/ 16 февраля 2012

Мне нужно написать программу, которая использует метод грубой силы, чтобы выяснить, как сделать изменения наиболее эффективно. Я немного смущен и мне любопытно, если я на правильном пути. Я пишу это на языке C.

Не использует жадный алгоритм.

Меня просто смущает, вот и все. В конце он должен вывести наиболее эффективные изменения: туни, луни, квартал, десять центов, никелей, пенни в указанном порядке. (Нравится 1 1 0 0 1 0.)

Я на правильном пути? Я немного сбит с толку относительно того, что я делаю, шестерка для циклов, очевидно, является ключом, и я добавляю каждую итерацию, но относительно того, что происходит концептуально, я немного запутался. 

#include <stdio.h>

int main(int argc, char *argv[]) {
    //Input
    int amount = 336;
    int bestSolution = amount;
    //Coins
    int toonies = 0, loonies = 0, quarters = 0, dimes = 0, nickels = 0, pennies = 0;
    int amountAfterToonies, amountAfterLoonies, amountAfterQuarters, amountAfterDimes, amountAfterNickels;
    //Counters
    int i, j, k, l, m, n;

    for (i = 0; i < amount / 200; i++) { //Finds amount 
        toonies++;
        amountAfterToonies = amount % 200;
        for (j = 0; j < amountAfterToonies / 100; j++) {
            loonies++;
            amountAfterLoonies = amountAfterToonies % 100;
            for (k = 0; k < amountAfterLoonies / 25; k++) {
                quarters++;
                amountAfterQuarters = amountAfterLoonies % 25;
                for (l = 0; l < amountAfterQuarters / 10; l++) {
                    dimes++;
                    amountAfterDimes = amountAfterQuarters % 10;
                    for (m = 0; m < amountAfterDimes / 5; m++) {
                        nickels++;
                        amountAfterNickels = amountAfterDimes % 5;
                    for (n = 0; n < amountAfterNickels; n++) {
                        pennies++;
                        sum = toonies + loonies + quarters + dimes + nickels + pennies;
                        if (sum < bestSolution) {
                            bestSolution = sum;
                        }
                    }
                }
            }
        }
    }
}
printf("%d %d %d %d %d %d\n", toonies, loonies, quarters, dimes, nickels, pennies);
printf("%d\n", bestSolution);
return 0;
}

Ответы [ 4 ]

3 голосов
/ 16 февраля 2012

Вы не находите самый эффективный способ. Вы находите все пути.

Я предлагаю вам что-то вроде: 

toonies=amount/200;
amount%=200;
loonies=amount/100;
amount%=100;
//and so on

(Даже если вы хотите сохранить циклы, разделите их - нет смысла использовать вложенные циклы)

0 голосов
/ 16 февраля 2012

Может быть, это бессонницы, добавленные к сумасшествию ... но это было слишком забавно, чтобы не отвечать ... 

#include <stdio.h>
struct coin {
   char *name;
   int     value;
   int     number;
};
#define NUMCOINS 7
int main(int argc, char *argv[]) {
   //Input
   int amount = 336;
   //Coins
   struct coin coins[NUMCOINS]={{"toonies", 200, 0},{"loonies",100,0},{ "four bit", 50,0},{ "two bit", 25,0},{"short bit",10,0},{ "nickels",5,0},{"pennies",1,0}};
   //Counters
   int i;

   for(i=0;i<NUMCOINS;i++)
     for (;amount >= coins[i].value; amount-=coins[i].value,coins[i].number++);

   for(i=0;i<NUMCOINS;i++)
     printf("%s %d \n",  coins[i].name, coins[i].number);


 return 0;
}
0 голосов
/ 16 февраля 2012

Ваше решение найдет все возможные решения.

Что вы подразумеваете под наиболее эффективным?

Шаг, который вам нужно добавить, - записать то, что вы считаете наиболее эффективным решением, и представить его в качестве ответа в конце.

Редактировать - Исправление; вы на правильном пути, но если вы проследите логику, которую вы впервые опубликовали, вы увидите, что вы никогда не сможете добавить копейки. Это связано с тем, что на первой итерации, где вы на самом деле получаете правильный результат, amountAfterDimes / 5 равно 0, поэтому вы никогда не добавляете ни копейки и, следовательно, никогда не находите правильный ответ.

Вы должны разрешить вашему поиску попробовать 0 каждой монеты, чтобы позволить ей опуститься до правильного ответа.

0 голосов
/ 16 февраля 2012

Алгоритм зависит от того, будет ли работать «жадный» алгоритм. Жадность работает в США, а я думаю, в Канаде, но не сработает, например, если бы было 15-центовое произведение или купюра в 3 доллара.

Для «жадного» вы берете общую сумму полученных изменений, многократно вычитаете наибольшую купюру / монету, пока сумма не станет меньше стоимости купюры / монеты, а затем возвращаетесь к следующей меньшей купюре / монете.

Несколько способов сделать это, но это может быть эффективно сделано в двух вложенных циклах и массиве, содержащем значения купюры / монеты. Или вы можете иметь N последовательных циклов, по одному на каждую купюру / монету. В этом случае петли не будут вложенными. По сути, каждый цикл будет 

while (amountDue >= bill_coin_values[i]) {
    bills_coins_to_dispense[i]++;
    amountDue -= bill_coin_values[i];
}

(Конечно, вышеприведенный цикл может быть заменен модульным делением, но на данном этапе разработки этот вопрос путает).

Но вставьте этот цикл в цикл, который увеличивает i по списку значений, и у вас есть версия с двумя циклами.

Т.е. внешний цикл будет выглядеть примерно так: 

int numSizes = 7;
int bill_coin_values[] = {200, 100, 50, 25, 10, 5, 1};
int bills_coins_to_dispense[7];
for (int i = 0; i < numSizes; i++) {
    bills_coins_to_dispense[i] = 0;
    <Above loop>
}
...