Рекурсивно определить, мржно ли заданную сумму денег разменять монетами по 3, 10, 15 копеек

@Selin-a · Регистрация: 02.06.2012

Author24 — интернет-сервис помощи студентам

Добрый день.
Подскажите, пожалуйста, где ошибка в решении следующей задачи: написать программу, которая рекурсивно позволяет определить, можно ли заданную сумму разменять монетами по 3, 10, 15 копеек.
Программа выдаёт результат только для суммы, равной 30. Сама я думаю, что ошибка во второй части программы, в месте вызова функции (номер строки 32).

Код следующий:

C++

bool divide(int sum, int money[])
{
    if (sum == 0)
    {
        return true;
    }
    else
    {
        for (int i = 0; i < sizeof(money); i++)
        {
            int tempsum = sum - money[i];
 
            if(divide(tempsum, money))
            {
                return true;
            }
        }
    }
 
    return false;
}
    
void _tmain(int argc, _TCHAR* argv[])
{
    int const size = 3;
    int A[size] = {3, 10, 15};
    int sum;
 
    printf("Enter summa:\n");
    scanf("%i", &sum);
 
    if(divide(sum,A))
    {
        printf("Yes");
    }
    else
    {
        printf("No");
    }
 
    printf("\n");
}

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

Заранее большое спасибо!

fanatdebian · 03.08.2012, 14:12

C

#include <stdio.h>
#define true 1
#define false 0
 
int check(int a, int some) {
    if (!(a % some)) {
         return (true);
    } else {
    return(false);
}
}
    
int main(){
    int a, t;
    int s[3]={3,10,15};
        printf("enter some value: ");
        scanf("%d", &a);
        for(t=0; t<=4; t++){
            if (check(a,s[t])){
                    printf("\nсумму %d можно разменять на %d\n", a, s[t]);
            } else {
                    printf("\nсумму %d нельзя разменять на %d\n", a, s[t]);
            }
    }
    return 0;
}

для новичка советую изучать голое си, по итогам изучения будет ясное представление что и как работает. Из плюсов изучение голого си, что очень много качественной документации с массой примеров и задач на все уровни становления молодого кодера. Харви Дейтел "Как программировать на Си", Стефан Кочан "Программирование на языке Си".
По рекурсии. Представь ситуацию что ты собираешь яблоки упавшие с дерева. В этом механизме сбора яблок есть фрагмент, который повторяется регулярно. Это наклон, взятия яблока, помещения яблока в корзину. Вот эти три действия можно поместить в отдельную функцию и к примеру вызывать ее в зависимости от количества упавших яблок. Ясно?

@splen · 03.08.2012, 15:32

Сообщение от fanatdebian

вызывать ее в зависимости от количества

Это, скорее, не рекурсия, а итерация.

Наиболее простой пример рекурсии - вычисление факториала: если нужно вычислить N!, то можно вычислить (N-1)! и результат умножить на N.

Характерная черта рекурсии - сведение задачи к аналогичной, как правило, более простой (в примере - сведение вычисления N! к к вычислению (N-1)!), а не явное повторение какой-либо операции.

В данной задаче можно рассуждать похожим образом: данную сумму S можно разменять указанным образом, если указанным образом можно разменять сумму S-3, S-5 либо S-15. При этом, как всегда, важно позаботиться о проверке условия завершения рекурсии (чтобы избежать бесконечной рекурсии).

@СашаН · 03.08.2012, 17:35

Привет Selin-a.
Я твой код слегка изменил, также и _tmain и _TCHAR.
Ты сама посмотри чтобы у тебя в среде всё работало.
У меня работает.

C

#include <stdio.h>
#define SIZE 3
 
int divide(int sum, int money[])
{
    int counter = 0;
    int temp_sum;
 
    temp_sum = sum;
    while(money[counter]) {
        temp_sum = sum - money[counter];
        if (0 == temp_sum) return 1;
        if (0 >  temp_sum) return 0;
        counter++;
    }
    return divide(temp_sum, money);
        
}
        
    
void main(int argc, char *argv[])
{
    int Arr[SIZE+1] = { 3, 10, 15, 0 }; // последний элемент НОЛЬ,
    int sum;                             // для использования в while().
 
    printf("Enter summa: ");
    scanf("%i", &sum);
 
    if(divide(sum,Arr))
    {
        printf("Yes");
    }
    else
    {
        printf("No");
    }
 
    printf("\n");
}

@Catstail · 03.08.2012, 17:37

Вот решение, основанное на идее Splen-а:

C++

#include "iostream.h"
 
int Chk(int n)
{
    if (n < 0) return 0;
    if ((n == 3) || (n == 10) || (n == 15)) return 1;
    return Chk(n-3) || Chk(n-10) || Chk(n-15);
}
 
int main(int argc, char* argv[])
{
    int k;
 
    while (1)
    {
        cout << "Enter sum  (0 - end)  ";
        cin >> k;
 
        if (k == 0) break;
 
        if (Chk(k))
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }
 
    return 0;
}

@Selin-a · 03.08.2012, 19:21 **[ТС]**

Большое всем спасибо за помощь

@splen 1728 / 1020 / 181 Регистрация: 03.06.2012 Сообщений: 1,220
	03.08.2012, 15:32	3
	Сообщение от fanatdebian вызывать ее в зависимости от количества Это, скорее, не рекурсия, а итерация. Наиболее простой пример рекурсии - вычисление факториала: если нужно вычислить N!, то можно вычислить (N-1)! и результат умножить на N. Характерная черта рекурсии - сведение задачи к аналогичной, как правило, более простой (в примере - сведение вычисления N! к к вычислению (N-1)!), а не явное повторение какой-либо операции. В данной задаче можно рассуждать похожим образом: данную сумму S можно разменять указанным образом, если указанным образом можно разменять сумму S-3, S-5 либо S-15. При этом, как всегда, важно позаботиться о проверке условия завершения рекурсии (чтобы избежать бесконечной рекурсии). 1

@Selin-a 0 / 0 / 0 Регистрация: 02.06.2012 Сообщений: 8
	03.08.2012, 19:21 [ТС]	6
	Большое всем спасибо за помощь 0