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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
yuliyayuliya28
4 / 4 / 0
Регистрация: 06.03.2011
Сообщений: 319
#1

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

26.12.2012, 22:58. Просмотров 377. Ответов 0
Метки нет (Все метки)

Здравствуйте помогите разобраться в рекурсии, задана последовательность монет состоящая из 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 минуты
не пойму что не правильно в алгоритме, помогите найти ошибку(
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.12.2012, 22:58
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Рекурсия. Определить, возможно ли из заданных монет получить сумму (C++):

Определить количество различных комбинаций монет, которые могут сложиться в определенную сумму - C++
Напишите программу, которая определяет количество различных комбинаций монет, которые могут сложиться в определенную сумму. Input: ...

Определить, возможно ли построить из заданных костяшек домино непрерывные цепочки - Prolog
Совершенно не знаю синтаксис языка Prolog, но надо написать программу для зачёта. d(2,6) это домино Есть задача: &quot;Написать программу,...

Получить цифры, составляющие сумму заданных чисел - PascalABC.NET
Помогите пожалуйста решить данную задачу с оператором выбора case. Даны цифры двух десятичных целых чисел: трехзначного а3а2а1 и...

Получить новый массив: сумму двух заданных - Basic
Всем добрый день.программисты,и просто те кто знает что такое basic и с чем его едят,помогите пожалуйста с заданием,не могу составить...

Найти максимально возможно количество монет в заначке - Pascal
Подскажите пожалуйста почему во 2 тесте минимум - 1. Формула n члена: T(k+1)=T(k)/2-x(k+1) T(k)=2(T(k+1)+x(k+1)) Предпоследний...

Для заданных a, b, c получить сумму максимального и минимального значений - Visual Basic .NET
h=max(a,b+c)+min(ac,bc) помогите пожалуйста, только установил, разобраться не получается пока что, а срочно нужно

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.12.2012, 22:58
Привет! Вот еще темы с ответами:

.NET 4.x Определить сумму заданных чисел - C#
Здравствуйте НАРОД, я нуб в С# и прошу ваших подсказок. Чем сможете помогите по задачкам, нужны решения вот на эти задачки: 14. Дано...

Определить сумму и произведение заданных элементов матрицы - Turbo Pascal
Дана квадратная матрица целых чисел. Определите сумму и произведение ненулевых элементов, которые находятся 1)ниже главной диагонали ...

Рекурсия. В заданном столбце матрицы определить сумму положительных элементов - Visual C++
Кто нибудь помогите написать программу по рекурсии. Вот само задание: В заданном столбце матрицы определить сумму положительных...

Определить, возможно ли получить число сложением чисел массива - Pascal
Задача. дано число A.Есть массив , в котором индекс- число, а значение в массиве - количество раз, которое можно складывать данное...


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

Или воспользуйтесь поиском по форуму:
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru