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

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

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

Найти в массиве натуральных чисел все группы элементов, имеющих одинаковую сумму цифр. C++
Среди чисел найти все те, которые можно представить в виде суммы квадратов двух натуральных чисел C++
C++ [C++] Вывести на экран все группы чисел
В массиве целых чисел найти и распечатать все пары одинаковых чисел C++
Циклы: Задано натуральное число n. Найти количество натуральных чисел, не превышающих n и не делящихся ни на одно из чисел 2, 3, 5 C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Andrey.K
 Аватар для Andrey.K
338 / 259 / 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
Сообщений: 183
01.06.2012, 19:41     Задано n чисел. Найти все группы по k чисел. #3
Andrey.K, Ты решил только для k=2, а в других случаях как?
Catstail
Модератор
 Аватар для Catstail
21423 / 10208 / 1662
Регистрация: 12.02.2012
Сообщений: 17,082
01.06.2012, 20:04     Задано n чисел. Найти все группы по k чисел. #4
Тут все серьезнее... Нужно построить все сочетания из N по k, и отобрать те, сумма чисел которых равна m.
Andrey.K
 Аватар для Andrey.K
338 / 259 / 15
Регистрация: 14.11.2010
Сообщений: 480
01.06.2012, 20:11     Задано n чисел. Найти все группы по k чисел. #5
Цитата Сообщение от Catstail Посмотреть сообщение
Тут все серьезнее... Нужно построить все сочетания из N по k, и отобрать те, сумма чисел которых равна m.
Ребят, я понял что решил не так, чем указывать мне на мою ошибку, лучше давайте найдем правильное решение.
Catstail
Модератор
 Аватар для Catstail
21423 / 10208 / 1662
Регистрация: 12.02.2012
Сообщений: 17,082
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
Модератор
 Аватар для Catstail
21423 / 10208 / 1662
Регистрация: 12.02.2012
Сообщений: 17,082
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
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 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 чисел.
Еще ссылки по теме:

Найти все пары двузначных чисел, которые, будучи записанными подряд, дают четырёхзначное число, нацело делящееся на сумму данных чисел C++
C++ Даны натуральное число n. Среди чисел 1, 2, …, n найти все те, которые можно представить в виде суммы квадратов двух натуральных чисел.
Даны натуральное число n. Среди чисел 1, 2, …, n найти все те, которые можно представить в виде суммы квадратов двух натуральных чисел 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 чисел.
Ответ Создать тему
Опции темы

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