Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
igor_m
0 / 0 / 5
Регистрация: 14.12.2014
Сообщений: 122
#1

Сколько существует подмножеств данных чисел, дающих в сумме значение меньше z? - C++

06.02.2015, 23:22. Просмотров 692. Ответов 5
Метки нет (Все метки)

помогите решить задачу

имеется n различных натуральных чисел. определите, сколько существует подмножеств данных чисел, дающих в сумме значение меньше z

Добавлено через 4 часа 1 минуту
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
#include <windows.h>
#pragma hdrstop
#include "pt4.h"
 
int kol = 0, s, a[20], n, z, j, k;
void search(int j);
 
void Solve()
{
    Task("BackRec6");
    int i;
    pt >> n >> z;
    for (i = 0; i < n; i++)
        pt >> a[i];
    for (i = 0; i < n; i++)
        search(i);
    pt << kol;
}
 
void search(int k)
{
    s += a[k];
    if (s < z)
        kol++;
    else
    {
        s -= a[k];
        for (j = k + 1; j < n; j++)
            search(j);
    }
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.02.2015, 23:22
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Сколько существует подмножеств данных чисел, дающих в сумме значение меньше z? (C++):

Рекурсия: определите подмножество данных чисел, дающих сумму меньше, чем Z и с количеством членов большим чем K
имеется n различных натуральных чисел. определите подмножество данных чисел,...

Определить сколько существует пар чисел, которые в сумме (по правилам планеты Олимпия) дают число Х
Мегапопулярный Дзидзьо посетил планету Олимпия, где живет много поклонников...

Задача о сумме подмножеств
Люди помогите, пожалуйста!!! Вот задача (Е-шка). Решал через ДП по профилю,...

Задача о сумме подмножеств
Здравствуйте, прошу помощи. Нужно реализовать алгоритм задачи о сумме...

Найти сколько чисел в массиве больше суммы или меньше разности чисел
Помогите решить задачу в С++. Нужно сформировать двумерный массив А(5,6) и...

Сколько существует мирных множеств натуральных чисел силы n?
Группа математиков проводит бои между натуральными числами. Результаты боя...

5
1XPLoade1
30 / 30 / 38
Регистрация: 23.01.2015
Сообщений: 174
07.02.2015, 19:05 #2
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
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <memory.h>
#include <time.h>
 
#define N 20
 
int main(int argc, char* argv[])
{
    int A[N] = { 0 };
    memset((void*)A, 0x00, sizeof(int) * N);
 
    srand((unsigned)time(NULL));
 
    int z = rand() % (2 * N) + 1;
    printf("z = %d\n\n", z);
 
    for (int i1 = 0; i1 < N; i1++)
    {
        A[i1] = rand() % 9 + 1;
        printf("%d ", A[i1]);
    }
 
    printf("\n\n");
 
    for (int i = 0; i < N; i++)
        for (int j = N - 1; j >= 0; j--)
        {
            int sum = 0, r = 0, B[N] = { 0 };
            for (int k = i; k < N - j - 1; k++)
            {
                sum += A[k]; B[r++] = A[k];
            }
 
            if (sum < z && sum > 0 && r > 1)
            {
                for (int t = 0; t < r; t++)
                    printf("%d ", B[t]);
 
                printf("sum = %d\n", sum);
            }
        }
 
    _getch();
 
    return 0;
}
0
Миниатюры
Сколько существует подмножеств данных чисел, дающих в сумме значение меньше z?  
1XPLoade1
30 / 30 / 38
Регистрация: 23.01.2015
Сообщений: 174
07.02.2015, 19:51 #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
50
51
52
53
54
55
56
#include <iostream>
#include <cstdlib>
#include <vector>
#include <ctime>
 
#define N 20
 
using namespace std;
 
int main(int argc, char* argv[])
{
    std::vector<int> A;
    
    std::srand((unsigned)std::time(NULL));
 
    int z = std::rand() % (2 * N) + 1;
    cout << "z = " << z << endl << endl;
 
    for (int i1 = 0; i1 < N; i1++)
    {
        int rnd_val = std::rand() % 9 + 1;
        A.push_back(rnd_val);
        cout << rnd_val << " ";
    }
 
    cout << endl << endl;
 
    std::vector<int>::const_iterator it;
    for (it = A.begin(); it != A.end(); it++)
    {
        std::vector<int>::const_iterator rev_it;
        for (rev_it = it + 1; rev_it != A.end(); rev_it++)
        {
            std::vector<int> B; int sum = 0;
            std::vector<int>::const_iterator fwd_it;
 
            for (fwd_it = it; fwd_it != rev_it; fwd_it++)
            {
                sum += *fwd_it; B.push_back(*fwd_it);
            }
 
            if (sum < z && sum > 0 && B.size() > 1)
            {
                std::vector<int>::const_iterator it2;
                for (it2 = B.begin(); it2 != B.end(); it2++)
                    cout << *it2 << " ";
 
                cout << "sum = " << sum << endl;
            }
        }
    }
 
    std::cin.get();
 
    return 0;
}
0
Миниатюры
Сколько существует подмножеств данных чисел, дающих в сумме значение меньше z?  
igor_m
0 / 0 / 5
Регистрация: 14.12.2014
Сообщений: 122
08.02.2015, 14:18  [ТС] #4
а можно без векторов и чтобы был счетчик этих подмножеств? выводить все варианты не нужно
0
1XPLoade1
30 / 30 / 38
Регистрация: 23.01.2015
Сообщений: 174
08.02.2015, 14:22 #5
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int count = 0;
for (int i = 0; i < N; i++)
        for (int j = N - 1; j >= 0; j--)
        {
            int sum = 0, r = 0, B[N] = { 0 };
            for (int k = i; k < N - j - 1; k++)
            {
                sum += A[k]; B[r++] = A[k];
            }
 
            if (sum < z && sum > 0 && r > 1)
            {
                for (int t = 0; t < r; t++)
                    printf("%d ", B[t]);
 
                printf("sum = %d\n", sum);
                count+=r;
            }
        }
printf("\ncount = %d\n",count);
Добавлено через 1 минуту
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
int count = 0;
std::vector<int>::const_iterator it;
    for (it = A.begin(); it != A.end(); it++)
    {
        std::vector<int>::const_iterator rev_it;
        for (rev_it = it + 1; rev_it != A.end(); rev_it++)
        {
            std::vector<int> B; int sum = 0;
            std::vector<int>::const_iterator fwd_it;
 
            for (fwd_it = it; fwd_it != rev_it; fwd_it++)
            {
                sum += *fwd_it; B.push_back(*fwd_it);
            }
 
            if (sum < z && sum > 0 && B.size() > 1)
            {
                std::vector<int>::const_iterator it2;
                for (it2 = B.begin(); it2 != B.end(); it2++)
                    cout << *it2 << " ";
 
                cout << "sum = " << sum << endl;
 
                count+=B.size();
            }
        }
    }
cout << "count = " << count << endl;
0
igor_m
0 / 0 / 5
Регистрация: 14.12.2014
Сообщений: 122
08.02.2015, 17:44  [ТС] #6
честно, не очень понятно. можешь просто в мой код внести изменения?
0
08.02.2015, 17:44
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.02.2015, 17:44
Привет! Вот еще темы с решениями:

Сколько существует чисел в интервале без дубликатов цифр
Есть интервал , 1 &lt;= l &lt; r &lt;= 10^18. Условие - отсутствие дублированных...

Класс, выясняющий, сколько среди заданных чисел пар, которые дают в сумме четное число
Добрый вечер. Помогите пожалуйста, нужно написать класс.:cry: Заданы три...

Сколько существует двухзначных, положительных чисел, сумма цифр которых равна 15
Подсчитать, сколько существует двухзначных, положительных чисел, сумма цифр...

Выяснить, сколько существует n-значных чисел, которые состоят только из нечётных цифр
&quot;Хорошим&quot; будем считать число, которое состоит только из нечетных цифр....


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

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

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