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

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

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

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

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

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

Циклы: Задано натуральное число n. Найти количество натуральных чисел, не превышающих n и не делящихся ни на одно из чисел 2, 3, 5 - C++
Завтра зачет не успеваю сделать занимаюсь prologom помогите кому не сложно!!! 1)(Циклы)Задано натуральное число n. Найти количество...

Найти в массиве натуральных чисел все группы элементов, имеющих одинаковую сумму цифр. - C++
Найти в массиве натуральных чисел все группы элементов, имеющих одинаковую сумму цифр. Массив вводится пользователем с клавы через пробелы....

[C++] Вывести на экран все группы чисел - C++
Вывести на экран все группы чисел , которые содержат нечётное количество чисел и нечётное количество единиц или нулей.

В массиве целых чисел найти и распечатать все пары одинаковых чисел - C++
В массиве целых чисел найти и распечатать все пары одинаковых чисел. За помощь буду очень благодарен. //В массиве целых чисел найти...

В заданном массиве целых чисел найти все пары чисел, удовлетворяющих условию - C++
Дан массив целых чисел а0, ..., аn-1. Найти все пары (аi, аi+1), такие, что аi = 0 и аi+1 кратно 2.

Среди чисел найти все те, которые можно представить в виде суммы квадратов двух натуральных чисел - C++
Помогите решить прогу плз. Условие: Дано натуральное число n. Среди чисел 1,2,...,n найти все те, которые можно представить в виде суммы...

13
Andrey.K
342 / 263 / 15
Регистрация: 14.11.2010
Сообщений: 482
01.06.2012, 19:38 #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;
}
0
rinat_w
89 / 85 / 4
Регистрация: 13.11.2011
Сообщений: 192
Завершенные тесты: 1
01.06.2012, 19:41 #3
Andrey.K, Ты решил только для k=2, а в других случаях как?
0
Catstail
Модератор
22709 / 11078 / 1795
Регистрация: 12.02.2012
Сообщений: 18,264
01.06.2012, 20:04 #4
Тут все серьезнее... Нужно построить все сочетания из N по k, и отобрать те, сумма чисел которых равна m.
0
Andrey.K
342 / 263 / 15
Регистрация: 14.11.2010
Сообщений: 482
01.06.2012, 20:11 #5
Цитата Сообщение от Catstail Посмотреть сообщение
Тут все серьезнее... Нужно построить все сочетания из N по k, и отобрать те, сумма чисел которых равна m.
Ребят, я понял что решил не так, чем указывать мне на мою ошибку, лучше давайте найдем правильное решение.
0
Catstail
Модератор
22709 / 11078 / 1795
Регистрация: 12.02.2012
Сообщений: 18,264
01.06.2012, 21:25 #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;
}
3
Миниатюры
Задано n чисел. Найти все группы по k чисел.  
rinat_w
01.06.2012, 21:39
  #7

Не по теме:

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

0
Catstail
Модератор
22709 / 11078 / 1795
Регистрация: 12.02.2012
Сообщений: 18,264
01.06.2012, 21:53 #8
Да, ладно...
0
qfisher
31 / 31 / 1
Регистрация: 24.05.2012
Сообщений: 156
01.06.2012, 22:09 #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
0
Toshkarik
1141 / 858 / 51
Регистрация: 03.08.2011
Сообщений: 2,386
Завершенные тесты: 1
01.06.2012, 22:19 #10
Тут delete, не в ту тему запостил код

Добавлено через 1 минуту
Catstail,
C++
1
2
delete [] A;
delete [] Z;
2
qfisher
31 / 31 / 1
Регистрация: 24.05.2012
Сообщений: 156
01.06.2012, 22:34 #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)
0
Татьяна19
0 / 0 / 0
Регистрация: 08.05.2012
Сообщений: 25
01.06.2012, 23:00  [ТС] #12
Блин, а никак попроще решить ее нельзя? преподаватель сразу поймет что код не я писала много уж слишком строк(((

Добавлено через 1 минуту
Всем спасибо за ответы, завтра попробую запустить, посмотрю, что будет)
0
qfisher
31 / 31 / 1
Регистрация: 24.05.2012
Сообщений: 156
04.06.2012, 03:05 #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;
}
0
qfisher
31 / 31 / 1
Регистрация: 24.05.2012
Сообщений: 156
06.06.2012, 00:41 #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;
}
0
06.06.2012, 00:41
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.06.2012, 00:41
Привет! Вот еще темы с ответами:

Среди чисел найти все те, которые можно представить в виде суммы квадратов двух натуральных чисел - C++
Дано натуральное число n. Среди чисел найти все те, которые можно представить в виде суммы квадратов двух натуральных чисел. (Определить...

Даны натуральное число n. Среди чисел 1, 2, …, n найти все те, которые можно представить в виде суммы квадратов двух натуральных чисел - C++
Даны натуральное число n. Среди чисел 1, 2, …, n найти все те, которые можно представить в виде суммы квадратов двух натуральных чисел.

Даны натуральное число n. Среди чисел 1, 2, …, n найти все те, которые можно представить в виде суммы квадратов двух натуральных чисел. - C++
Собственно само задание. 5). Даны натуральное число n. Среди чисел 1, 2, …, n найти все те, которые можно представить в виде суммы...

Найти все пары двузначных чисел, которые, будучи записанными подряд, дают четырёхзначное число, нацело делящееся на сумму данных чисел - C++
Два двузначных числа, записанных подряд, образуют четырехзначное число, которое нацело делится на их сумму. Найти все такие числа. ...


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

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

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