Форум программистов, компьютерный форум CyberForum.ru

Рекурсия. Определить, возможно ли из заданных монет получить сумму - C++

Восстановить пароль Регистрация
 
yuliyayuliya28
3 / 3 / 0
Регистрация: 06.03.2011
Сообщений: 319
26.12.2012, 22:58     Рекурсия. Определить, возможно ли из заданных монет получить сумму #1
Здравствуйте помогите разобраться в рекурсии, задана последовательность монет состоящая из n элементов, и сумма,
необходимо определить возможно ли из заданных монет получить эту сумму;
Помогите пожалуйста,ломаю голову не понимаю, даже как записать на цифрах

Например дано 3 5 2 и сумма 6 , значит нельзя, а сумма 7 можно;

Добавлено через 35 минут
bool f(int sum,int n)
{
return f(sum-a,n)
}

5 6 7 8 4, sum = 12 ...... 12-5 =8, 8 - 6=2, 2-7 =-5, но сумма 12 модет быть из 8 и 4х((((

Добавлено через 25 минут
Попыталась скомпоновать, но не понимаю почему ошибки,


и смысл этой строки не очень понятен return sum (localSum - a[lastPos],lastPos-1) + // используем элемент a[lastPos]
sum (localSum,lastPos-1); // не используем элемент a[lastPos]

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include "stdafx.h"
#include <iostream>
#include <vector>
#include <stdio.h>
using namespace std;
 
vector<int> a;
 
int sum(int localSum, int lastPos)
{
    if (localSum == 0 && lastPos == -1) // перебрали все элементы и набрали сумму
        return 1;
    if (localSum != 0 && lastPos == -1) // перебрали все элементы, но не набрали сумму
        return 0;
    if (a[lastPos] <= localSum) // можно набрать сумму с элементом a[lastPos]
        return sum (localSum - a[lastPos],lastPos-1) + // используем элемент a[lastPos]
               sum (localSum,lastPos-1);               // не используем элемент a[lastPos]
    else
        return sum (localSum,lastPos-1); 
}
        
    
void main(int argc, char *argv[])
{
    int SUM,n;
    vector<int> a;
    cin>>SUM;
    cin>>n;
    a.resize(n);
    for (int i=0;i<n;i++)
     cin>>a[i];
 
    printf("Enter summa: ");
    scanf("%i", &sum);
 
    if(sum(SUM,n))
    {
        printf("Yes");
    }
    else
    {
        printf("No");
    }
 
    printf("\n");
}
Добавлено через 32 минуты
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include "stdafx.h"
#include <iostream>
 
#include <stdio.h>
using namespace std;
 
 
 
int sum(int localSum, int a[lastPost])
{   
    if (localSum == 0 && lastPos == -1) // перебрали все элементы и набрали сумму
        return 1;
    if (localSum != 0 && lastPos == -1) // перебрали все элементы, но не набрали сумму
        return 0;
    if (a[lastPos] <= localSum) // можно набрать сумму с элементом a[lastPos]
        return sum (localSum - a[lastPos],lastPos-1);// используем элемент a[lastPos]
              
    else
        return sum (localSum,lastPos-1); 
}
        
    
void main(int argc, char *argv[])
{
    int SUM;
    int *a,n;
    cout<<"SUmma"<<endl;
    cin>>SUM;
    cout<<"n"<<endl;
    cin>>n;
    a=new int[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
 
    if(sum(SUM,a))
    {
        printf("Yes");
    }
    else
    {
        printf("No");
    }
 
    printf("\n");
}

Возникают ошибки c тем что lastPos не определён, как передавать массив, и его размер сразу

Добавлено через 8 минут
сделала чтобы в функцию подавалось 3 параметра, но алгоритм не верен, помогите пожалуйста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include "stdafx.h"
#include <iostream>
 
#include <stdio.h>
using namespace std;
 
 
 
bool sum(int localSum, int a[],int lastPos)
{   
    if (localSum == 0 && lastPos == -1) // перебрали все элементы и набрали сумму
        return 1;
    if (localSum != 0 && lastPos == -1) // перебрали все элементы, но не набрали сумму
        return 0;
    if (a[lastPos] <= localSum) // можно набрать сумму с элементом a[lastPos]
        {cout<<localSum<<endl;
        return sum (localSum - a[lastPos],a,lastPos-1);// используем элемент a[lastPos]
    }      
    else
        cout<<localSum<<endl;
        return sum (localSum,a,lastPos-1); 
}
        
    
void main(int argc, char *argv[])
{
    int SUM;
    int *a,n;
    cout<<"SUmma"<<endl;
    cin>>SUM;
    cout<<"n"<<endl;
    cin>>n;
    a=new int[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
 
    if(sum(SUM,a,n))
    {
        printf("Yes");
    }
    else
    {
        printf("No");
    }
 
    printf("\n");
}
Добавлено через 1 час 42 минуты
не пойму что не правильно в алгоритме, помогите найти ошибку(
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.12.2012, 22:58     Рекурсия. Определить, возможно ли из заданных монет получить сумму
Посмотрите здесь:

C++ Рекурсия: найти сумму элементов массива
C++ Рекурсия. Составьте программу, которая для заданных значений n и m, определит номер оставшегося в кругу человека
C++ За два взвешивания определить которая из пяти монет имеет вес, отличный от остальных.
Рекурсия: вычислить сумму ряда C++
C++ Найти сумму чисел заданных ввиде строки
C++ Определить количество различных комбинаций монет, которые могут сложиться в определенную сумму
Получить цифры числа, равного разности заданных чисел C++
Рекурсия. Найти сумму чисел от 1 до n C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

Текущее время: 21:20. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru