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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Вычислить сумму S = P1 + P2 произведения P1 четных элементов массива xi и произведения P2 четных элементов массива yi , i = 1, 2, 3 http://www.cyberforum.ru/cpp-beginners/thread747053.html
Пожалуйста решите. Вычислить сумму S = P1 + P2 произведения P1 четных элементов массива xi и произведения P2 четных элементов массива yi , i = 1, 2, 3
C++ Определить, делителем каких чисел из целых a, b, c является число k Пожалуйста решите (очень нужно) Определить, делителем каких чисел из целых a, b, c является число k http://www.cyberforum.ru/cpp-beginners/thread747045.html
C++ Модификация игр
Всем привет! Суть вопроса: Какую игру выбрать для модификации, что бы понять основы игростроения. Детали ниже! :) Я достаточно знаю язык С++, чтобы понять практически любой. Проблема в том что...
C++ typedef и указатель на функцию
Здравствуйте! Помогите пожлауйста с пониманем одного момента... Так вот, есть оператор typedef.Он насколько я понял, обьявляет синоним.Напрмер: typedef int my; my up; То есть my==int, и...
C++ что то типа крестики нолики http://www.cyberforum.ru/cpp-beginners/thread747028.html
допустим : 1 2 3 такое а поле в как с я ввожу координаты, например: а1 в2 с3...
C++ Реализовать распознавание штрих-кода на изображении и их расшифровку Добрый день, нужна помощь с реализацией. Задание: Реализовать распознавание штрих-кода на изображении и их расшифровку. У нас дана, к примеру, фотография с обычным штрих (бар) кодом (без сложностей... подробнее

Показать сообщение отдельно
yuliyayuliya28
4 / 4 / 0
Регистрация: 06.03.2011
Сообщений: 319

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

26.12.2012, 22:58. Просмотров 385. Ответов 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
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru