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

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

Войти
Регистрация
Восстановить пароль
 
Татьяна19
0 / 0 / 0
Регистрация: 08.05.2012
Сообщений: 25
#1

Задано n чисел. Найти все группы по k чисел. - C++

01.06.2012, 19:13. Просмотров 979. Ответов 13
Метки нет (Все метки)

Задано n произвольных натуральных чисел. Найти все группы по k чисел, сумма которых равна заданному числу m. Что-то не знаю как делать
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.06.2012, 19:13     Задано n чисел. Найти все группы по k чисел.
Посмотрите здесь:

Найти в массиве натуральных чисел все группы элементов, имеющих одинаковую сумму цифр. C++
C++ Дано n различных чисел, напечатать все возможные перестановки этих чисел
C++ [C++] Вывести на экран все группы чисел
Найти все пары двузначных чисел, которые, будучи записанными подряд, дают четырёхзначное число, нацело делящееся на сумму данных чисел C++
C++ Дается n чисел, нужно вывести сначала все нечетные а затем все четные (найти ошибку)
Дано n различных натуральных чисел (n=5). Напечатать все перестановки этих чисел C++
Задано целое число N. Найдите сумму простых чисел до N C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Andrey.K
340 / 261 / 15
Регистрация: 14.11.2010
Сообщений: 480
01.06.2012, 19:38     Задано n чисел. Найти все группы по k чисел. #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
#include <iostream>
#include <conio.h>
using namespace std;
int main()
{
    int m,n;
    cout<<"Vvedite chislo m: ";cin>>m;
    cout<<"Vvedite kol-vo naturalnix chisel: ";cin>>n;
    int* mas=new int[n];
    for(int i=0;i<n;i++)
    {
        cout<<"Vvedite ["<<i<<"] chislo: ";cin>>mas[i];
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(mas[i]+mas[j]==m && i!=j) cout<<mas[i]<<" "<<mas[j]<<endl;
        }
    }
    getch();
    return 0;
}
rinat_w
89 / 85 / 4
Регистрация: 13.11.2011
Сообщений: 192
Завершенные тесты: 1
01.06.2012, 19:41     Задано n чисел. Найти все группы по k чисел. #3
Andrey.K, Ты решил только для k=2, а в других случаях как?
Catstail
Модератор
22142 / 10616 / 1728
Регистрация: 12.02.2012
Сообщений: 17,664
01.06.2012, 20:04     Задано n чисел. Найти все группы по k чисел. #4
Тут все серьезнее... Нужно построить все сочетания из N по k, и отобрать те, сумма чисел которых равна m.
Andrey.K
340 / 261 / 15
Регистрация: 14.11.2010
Сообщений: 480
01.06.2012, 20:11     Задано n чисел. Найти все группы по k чисел. #5
Цитата Сообщение от Catstail Посмотреть сообщение
Тут все серьезнее... Нужно построить все сочетания из N по k, и отобрать те, сумма чисел которых равна m.
Ребят, я понял что решил не так, чем указывать мне на мою ошибку, лучше давайте найдем правильное решение.
Catstail
Модератор
22142 / 10616 / 1728
Регистрация: 12.02.2012
Сообщений: 17,664
01.06.2012, 21:25     Задано n чисел. Найти все группы по k чисел. #6
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Вот решение:

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include "iostream.h"
 
void check_comb(int *A, int k, int *Z, int m)
{
    int i,j,s=0;
    for (i=0; i<k; i++)
    {
               j=A[i];
           s=s+Z[j];
    }
 
    if (s == m)
    {
        for (i=0; i<k; i++)
        {
            j=A[i];
            cout << Z[j] << " ";
        }
        cout << endl << endl;
    }
    
}
 
int main(int argc, char* argv[])
{
 
    int *A,*Z;
    int i,j,n,k,m,q;
 
    cout << "n=";
    cin >> n;
 
    Z=new int[n];
 
    for (i=0; i<n; i++)
    {
        cout << "Z[" << i << "]=";
        cin >> Z[i];
    }
 
    cout << "k=";
    cin >> k;
 
    cout << "m=";
    cin >> m;
 
    A=new int[k];
 
    for (i=0; i<k; i++) A[i]=i;
 
    while (1)
    {
        check_comb(A,k,Z,m);
 
        q=0;
 
        for (j=k-1; j>=0; j--)
            if (A[j] != (n-k+j))
            {
                q=-1;
                A[j]++;
                for (i=j+1; i<k; i++)
                    A[i]=A[i-1]+1;
                break;
            }
 
        if (q == 0) break;
 
    }
 
    delete A;
    delete Z;
 
    return 0;
}
Миниатюры
Задано n чисел. Найти все группы по k чисел.  
rinat_w
01.06.2012, 21:39
  #7

Не по теме:

Catstail, ты крут!! молодец, задачка то сложная

Catstail
Модератор
22142 / 10616 / 1728
Регистрация: 12.02.2012
Сообщений: 17,664
01.06.2012, 21:53     Задано n чисел. Найти все группы по k чисел. #8
Да, ладно...
qfisher
30 / 30 / 1
Регистрация: 24.05.2012
Сообщений: 156
01.06.2012, 22:09     Задано n чисел. Найти все группы по k чисел. #9
а если вот так ввести.)


n=7
Z[0]=32
Z[1]=4
Z[2]=54
Z[3]=5
Z[4]=3
Z[5]=31
Z[6]=31
k=3
m=90
Toshkarik
1139 / 856 / 51
Регистрация: 03.08.2011
Сообщений: 2,383
Завершенные тесты: 1
01.06.2012, 22:19     Задано n чисел. Найти все группы по k чисел. #10
Тут delete, не в ту тему запостил код

Добавлено через 1 минуту
Catstail,
C++
1
2
delete [] A;
delete [] Z;
qfisher
30 / 30 / 1
Регистрация: 24.05.2012
Сообщений: 156
01.06.2012, 22:34     Задано n чисел. Найти все группы по k чисел. #11
Цитата Сообщение от Catstail Посмотреть сообщение
while (1)
* * {
* * * * check_comb(A,k,Z,m);
q=0;
for (j=k-1; j>=0; j--)
* * * * * * if (A[j] != (n-k+j))
* * * * * * {
* * * * * * * * q=-1;
* * * * * * * * A[j]++;
* * * * * * * * for (i=j+1; i<k; i++)
* * * * * * * * * * A[i]=A[i-1]+1;
* * * * * * * * break;
* * * * * * }
if (q == 0) break;
}
можно так заменить

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
do
    {
        check_comb(A,k,Z,m);
 
        q=0;
 
        for (j=k-1; j>=0; j--)
            if (A[j] != (n-k+j))
            {
                q=-1;
                A[j]++;
                for (i=j+1; i<k; i++)
                    A[i]=A[i-1]+1;
                break;
            }
    }
while (q!=0)
Татьяна19
0 / 0 / 0
Регистрация: 08.05.2012
Сообщений: 25
01.06.2012, 23:00  [ТС]     Задано n чисел. Найти все группы по k чисел. #12
Блин, а никак попроще решить ее нельзя? преподаватель сразу поймет что код не я писала много уж слишком строк(((

Добавлено через 1 минуту
Всем спасибо за ответы, завтра попробую запустить, посмотрю, что будет)
qfisher
30 / 30 / 1
Регистрация: 24.05.2012
Сообщений: 156
04.06.2012, 03:05     Задано n чисел. Найти все группы по k чисел. #13
улучшил, корректная обработка если на вход подаешь 4 числа - 11(теперь на выходе повторяющиеся комбинации отсутствуют)
k = 2
sum = 22

буду признателен если найдете ошибки или оптимизируете .)

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include <iostream>
using namespace std;
 
void print_line()
{
    cout << endl << "*********************************" << endl << endl;
}
 
int main(int argc, char *argv[])
{
    int i,j,n,k,sum;
 
    // задаем количество элементов массива
    cout << "n=";
    cin >> n;
 
    int *input=new int[n];
 
    // вводим данные массива
    for (i=0; i<n; i++)
    {
        cout << "input[" << i << "]=";
        cin >> input[i];
    }
 
    // количество элементов в группе
    cout << "k=";
    cin >> k;
 
    // искомая сумма группы
    cout << "sum=";
    cin >> sum;
 
    // инициализация двумерного массива
    int *minmax = new int[n];
 
    //
    for (j = 0; j < n ; j++)
    {
        minmax[j] = j;
    }
 
    // определяем массив индексов по возрастанию входного массива
    bool is_changed;
    do
    {
        is_changed = false;
        for (i=1; i<n; i++)
        {
            if (input[minmax[i-1]] > input[minmax[i]])
            {
                // обмен
                int temp;
                temp = minmax[i];
                minmax[i] = minmax[i-1];
                minmax[i-1] = temp;
                is_changed = true;
            }
            else if(input[minmax[i]] == input[minmax[i-1]])
            {
                minmax[i] = minmax[i-1];
            }
        }
    }
    while (is_changed);
 
    //  инициализация набора
    int *nabor = new int[k];
 
    for (i=0; i < k; i++)
    {
        nabor[i] = i;
    }
 
    print_line();
    cout << "Элементы:" << endl;
 
    // далее нужно перебирать сочетания
    do
    {
        // находим сумму текущего набора
        int s=0;
        for (i=0; i<k; i++)
        {
            s += input[minmax[nabor[i]]];
        }
 
        // если сумма совпадает то вывод элементов текущей группы
        if (s == sum)
        {
            cout << endl;
 
            for (i=0; i<k; i++)
            {
                cout << input[minmax[nabor[i]]] << "\t";
            }
 
            cout << endl;
        }
 
        is_changed = false;
 
        // здесь формируется следующий набор
        for (j=k-1; j>=0; j--)
        {
            for (i=nabor[j]+1; i<n-k+j+1; i++)
            {
                if (minmax[nabor[j]] != minmax[i])
                {
                    nabor[j] = i;
                    is_changed = true;
 
                    for (int m = j+1; m < k; m++)
                    {
                        nabor[m] = nabor[m-1] + 1;
                    }
 
                    break;
                }
            }
 
            if (is_changed) break;
        }
    }
    while (is_changed);
 
    print_line();
 
    delete[] minmax;
    delete[] nabor;
    delete[] input;
 
    return 0;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.06.2012, 00:41     Задано n чисел. Найти все группы по k чисел.
Еще ссылки по теме:

В файле a.txt задано 5 целых чисел. Вывести их согласно предложенному формату C++
Для каждой группы чисел найти минимальное, максимальное и среднеарифметическое C++
В заданном массиве целых чисел найти все пары чисел, удовлетворяющих условию C++
Задано число. Найти пару чисел с наибольшим общим кратным, которые равны в сумме исходному числу C++

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

Или воспользуйтесь поиском по форуму:
qfisher
30 / 30 / 1
Регистрация: 24.05.2012
Сообщений: 156
06.06.2012, 00:41     Задано n чисел. Найти все группы по k чисел. #14
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include <iostream>
using namespace std;
 
void print_line()
{
    cout << endl << "*********************************" << endl << endl;
}
 
int main(int argc, char *argv[])
{
    int i,j,n,k,sum;
 
    // задаем количество элементов массива
    cout << "Количество натуральных чисел, n = ";
    cin >> n;
 
    int *input=new int[n];
 
    // вводим данные массива
    for (j=0; j<n; j++)
    {
        cout << j+1 << " число = ";
        cin >> input[j];
 
        // формируем массив по возрастанию между делом.)
        i = j;
        int temp;
        while (input[i]<input[i-1] && i>0)
        {
            temp = input[i-1];
            input[i-1] = input[i];
            input[i] = temp;
            i--;
        }
    }
 
    // количество элементов в группе
    cout << "Количество чисел группы, k = ";
    cin >> k;
    // искомая сумма группы
    cout << "Сумма группы, sum = ";
    cin >> sum;
 
    //  инициализация набора
    int *nabor = new int[k];
 
    for (i=0; i < k; i++)
    {
        nabor[i] = i;
    }
 
    print_line();
    cout << "Элементы:" << endl;
 
    bool is_changed;
    // далее нужно перебирать сочетания
    do
    {
        // находим сумму текущего набора
        int s=0;
        for (i=0; i<k; i++)
        {
            s += input[nabor[i]];
        }
 
        // если сумма совпадает то вывод элементов текущей группы
        if (s == sum)
        {
            cout << endl;
 
            for (i=0; i<k; i++)
            {
                cout << input[nabor[i]] << "\t";
            }
 
            cout << endl;
        }
 
        is_changed = false;
 
        // здесь формируется следующий набор
        for (j=k-1; j>=0; j--)
        {
            for (i=nabor[j]+1; i<n-k+j+1; i++)
            {
                if (input[nabor[j]] != input[i])
                {
                    nabor[j] = i;
                    is_changed = true;
 
                    for (int m = j+1; m < k; m++)
                    {
                        nabor[m] = nabor[m-1] + 1;
                    }
 
                    break;
                }
            }
 
            if (is_changed) break;
        }
    }
    while (is_changed);
 
    print_line();
 
    delete[] nabor;
    delete[] input;
 
    return 0;
}
Yandex
Объявления
06.06.2012, 00:41     Задано n чисел. Найти все группы по k чисел.
Ответ Создать тему
Опции темы

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