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

мне нужна помощь по курсовой работе!!! - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.92
ruslan000
0 / 0 / 0
Регистрация: 19.09.2011
Сообщений: 9
19.09.2011, 22:18     мне нужна помощь по курсовой работе!!! #1
(Делать нужно на С++)
Задание такое: Задан массив натуральных чисел P[n]. Найти минимальное натуральное число, не представимое суммой никаких элементов массива P. Сумма может состоять из одного слогаемого, но каждый элемент массива может входить в неё только 1 раз.

Добавлено через 1 час 51 минуту
а всё, кажись разобрался=)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
alkagolik
 Аватар для alkagolik
1510 / 616 / 79
Регистрация: 15.07.2011
Сообщений: 3,552
19.09.2011, 22:45     мне нужна помощь по курсовой работе!!! #2
вычисляем минимальное число типа int (в разных архитектурах разные длины типов поэтому для переносимости кода ее надо именно вычислить)
C++
1
2
3
int chislo_byte = sizeof(int), min_type_int;
min_type_int = -1 * pow(2.0, 8 * chislo_byte) /* могут возникнуть проблемы с типом, pow() 
принимает float/double надо явно преобразовать*/
и двойным циклом проверяем элементы массива на соответствие условию, если нашлась такая сумма 1го или 2х элементов что равна min_type_int, то инкрементим min_type_int и цикл по новой.
Конечно легче узнать минимальное значение средствами STL, но думаю что это пока не понадобится.
ruslan000
0 / 0 / 0
Регистрация: 19.09.2011
Сообщений: 9
19.09.2011, 22:48  [ТС]     мне нужна помощь по курсовой работе!!! #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
#include<iostream.h>
void main(void)
{
 int* a;
 int j,i,t,k,N,n;
 cout<<"Vvedite kolichestvo elementov"<<endl;
 cin>>n;
 a=new int[n];
 cout<<"Vvedite elementi"<<endl;
 for(i=0;i<n;i++)
 cin>>a[i];
 for(i=0;i<n-1;i++)
 for(j=i+1;j<n;j++)
 if(a[i]>a[j])
 {
 t=a[j];
 a[j]=a[i];
 a[i]=t;
 }
 k=0;
 N=0;
 while(k!=n && a[k]<=N+1)
 {
 N=N+a[k];
 k++;
 }
 cout<<"Minimalnoe chislo, ne predstavimoe summoi nikakih elementov: ";
 cout<<N+1<<endl;
}
Добавлено через 1 минуту
я тупо не знаю как оформить курсовую=)

 Комментарий модератора 
Используйте теги форматирования кода!
alkagolik
 Аватар для alkagolik
1510 / 616 / 79
Регистрация: 15.07.2011
Сообщений: 3,552
19.09.2011, 23:57     мне нужна помощь по курсовой работе!!! #4
не правда ли так более приятно читать код?
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
int main(){
    int* a;
    int t,k,N,n;
 
    std::cout<<"Vvedite kolichestvo elementov"<< std::endl;
    std::cin>>n;
 
    a=new int[n];
 
    std::cout<<"Vvedite elementi"<<std::endl;
 
    for(int i=0;i<n;i++)
        a[i] = i - n / 2;
 
    /* вывод массива */
    for(int i = 0; i < n; ++i)
        std::cout << a[i] << ' ';
 
    for(int i=0;i<n-1;i++)
        for(int j=i+1;j<n;j++)
            if(a[i]>a[j]){
                t=a[j];
                a[j]=a[i];
                a[i]=t;
            }
 
    k=0; N=0;
 
    /* не понимаю назначения этого цикла */
    while(k!=n && a[k]<=N+1){
        N=N+a[k];
        k++;
    }
 
    std::cout<<"\nMinimalnoe chislo, ne predstavimoe summoi nikakih elementov: ";
    std::cout<<N+1<<std::endl;
 
    return 0;
}
теперь по сути: в программе я сделал 3 изменения
1. заполнение массива самостоятельно - стр 14
2. вывод массива на экран - стр 17, 18
3. добавил символ переноса строки '\n' в строковый литерал - стр 36
дальше - результат работы программы
Код
$ ./tmp 
Vvedite kolichestvo elementov
45
Vvedite elementi
-22 -21 -20 -19 -18 -17 -16 -15 -14 -13 -12 -11 -10 -9 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4
 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 
Minimalnoe chislo, ne predstavimoe summoi nikakih elementov: -42
как видно из результата: во - первых программа не справилась с задачей поскольку -22 +(-20) = -42, а во вторых разве -42 минимальное натуральное число (представимое машиной)? -100, например меньше чем - 42.

Последнее int t,k,N,n; дайте им осмысленные имена чтобы код программы читался "интуитивно"

Добавлено через 31 минуту
стоп стоп, мой косяк. натуральные числа больше нуля

Добавлено через 14 минут
короче я никак не могу въехать в условие. Пример:
дам массив 3, 5, 8, 1
искомое натуральное число чему должно быть равно? и почему? ведь каждое нат число есть сумма единиц, и следовательно нет такого числа чтобы отвечало условию. Но если дан массив без 1:
2,4,6,12 чему тогда будет равняться искомое число? 3 или 1?
ruslan000
0 / 0 / 0
Регистрация: 19.09.2011
Сообщений: 9
20.09.2011, 16:13  [ТС]     мне нужна помощь по курсовой работе!!! #5
допустим вводим 1 1 3 7
он тебе выдаст 6
1+1+3=5
7=7
первое число, не представимое суммой никаких элементов - 6
вообще это для упорядоченного массива, я не знаю как сделать для не упорядоченного.
Gepar
 Аватар для Gepar
1173 / 529 / 20
Регистрация: 01.07.2009
Сообщений: 3,512
20.09.2011, 16:37     мне нужна помощь по курсовой работе!!! #6
Ну так отсортируй массив:
C++
1
2
3
4
#include <algorithm>
...
 
sort(a,a+n);
alkagolik
 Аватар для alkagolik
1510 / 616 / 79
Регистрация: 15.07.2011
Сообщений: 3,552
20.09.2011, 17:42     мне нужна помощь по курсовой работе!!! #7
ruslan000, наскоро я вижу пока только так:
1. сортируем массив по возрастанию (или убыванию, как угодно) и проверяем наличие в нем единицы
1.2. если да, то проверяем тот случай что каждый элемент больше предыдущего на n = 1; 2
1.2.3. если да, то искомое число сумма всех элементов + 1.
1.2.4. иначе пока не вижу решения
1.3.иначе искомое число 1.

Добавлено через 38 минут
Gepar, ну массив сортировать, это и так понятно, думаю даже что лучше и без STL. Дальше виже так, что берется число, проверяется на принадлежность к массиву, если нет, то раскладывается в ряды и проверяется на наличие элементов рядов массиву.
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
20.09.2011, 18:02     мне нужна помощь по курсовой работе!!! #8
Не то, удалено все.
alkagolik
 Аватар для alkagolik
1510 / 616 / 79
Регистрация: 15.07.2011
Сообщений: 3,552
20.09.2011, 18:37     мне нужна помощь по курсовой работе!!! #9
и в довершение Thinker, покажу "на пальцах". Дан массив mass[4] = {1, 3, 5, 8}. Вспоминая комбинаторику создаем массив для сумм всех сочетаний без повторений в данном случае 15. Заполняем его суммами сочетаний без повторений, т.е. n = 4, m = {1, 2, 3, 4}
C++
1
2
3
int *mass_summ;
n_sochtaniy = ...
mass_summ = new int [n_sochetaniy]
в данном примере mass_summ = {1, 3, 5, 8, 4, 6, 9, 8, 11, 13, 8, 12, 14, 16, 17}
ищем разницу mass_summ[i + 1] - mass_summ[i] >1, если да то... пока еще не придумал иначе max(mass_summ[i]) + 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
32
33
34
35
36
37
38
39
40
41
42
#include<iostream>
#include<stdlib.h>  //для рандомных чисел
#define SIZE_M  20
 
bool check_min_max(int min, int max);
 
int main(){
    int mass[SIZE_M];
    mass[0] = 1;
 
    for(int i = 1; i != SIZE_M; ++i)
        mass[i] = rand() % 10;
 
    std::cout << "исходный массив \n";
    for(int i = 0; i != SIZE_M; ++i)
        std::cout << mass[i] << ' ';
    std::cout << std::endl << std::endl;
 
    for(int i = 0; i != SIZE_M - 1 /*не выход за пределы массвиа при k=i+1*/; ++i)
        for(int k = i + 1; k < SIZE_M; ++k){
            if(check_min_max(mass[i], mass[k])){ //если mass[i] > mass[k]
                /* меняем их местами */
                mass[k] += mass[i];
                mass[i] = mass[k] - mass[i];
                mass[k] -= mass[i];
            }
        }
 
    std::cout << "упорядоченный массив \n";
    for(int i = 0; i != SIZE_M; ++i)
        std::cout << mass[i] << ' ';
    std::cout << std::endl << std::endl;
 
    int iskomoe = 1;
    
    return 0;
}
 
bool check_min_max(int min, int max){
    bool check = min > max ? true : false;
    return check;
}
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
20.09.2011, 18:44     мне нужна помощь по курсовой работе!!! #10
Возможно, задача требует 2^n переборов. Вот если бы после сортировки элементы массива образовывали гипервозрастающую (гиперубывающую) последовательность, то задачу очень просто решить, а в общем случае без перебора всех вариантов могут ошибки быть.

Добавлено через 4 минуты
alkagolik, по идее, ищем все сочетания из n по 1, из n по 2,..., из n по n и составляем из данных сумм массив (или список) упорядоченный. Смотрим на s[i]-s[i-1]. Если s[i]-s[i-1]>1, то искомое число s[i-1]+1.
alkagolik
 Аватар для alkagolik
1510 / 616 / 79
Регистрация: 15.07.2011
Сообщений: 3,552
20.09.2011, 18:46     мне нужна помощь по курсовой работе!!! #11
Thinker, и я об том. при массиве mass[n]; n = 4, m = {1, 2, 3, 4} и не забыть отсортировать массив сумм
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
20.09.2011, 19:00     мне нужна помощь по курсовой работе!!! #12
Цитата Сообщение от alkagolik Посмотреть сообщение
короче задача разобрана по косточкам.
Да, но если в массиве n=1000 элементов, то для массива сумм понадобится 2^1000 элементов.
Нужны уточнения на ограничения параметра n. При большом n массив сумм ни в какие ворота (то есть память) не влезет

Очень кажется, что на исходный массив ограничения должны быть наложены, иначе сложность алгоритма ОЧЕНЬ высокая, да и памяти надо МНОГО.
alkagolik
 Аватар для alkagolik
1510 / 616 / 79
Регистрация: 15.07.2011
Сообщений: 3,552
20.09.2011, 19:01     мне нужна помощь по курсовой работе!!! #13
Thinker, не нужно уточнений. курсовик нормальный (серьезный если можно так сказать). На применение длинной арифметики и вычисление факториалов через string. Ну а фактически надо исходить конечно из памяти. Ведь на диске с любой программой, игрой всегда пишется сколько ей нужно ОП для корректной работы. Т.е. вычислить при каком "n - размерность массива" программа просто уложится в объем ОП. Или менять алгоритм в корне.
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
20.09.2011, 19:06     мне нужна помощь по курсовой работе!!! #14
Цитата Сообщение от alkagolik Посмотреть сообщение
Thinker, не нужно уточнений...
Пусть так. Если более оптимальных алгоритмов нет для такой задачи, тогда курсовая работа и правда хорошая
alkagolik
 Аватар для alkagolik
1510 / 616 / 79
Регистрация: 15.07.2011
Сообщений: 3,552
21.09.2011, 04:11     мне нужна помощь по курсовой работе!!! #15
я тут покурил и вот что подумал. Вычислять длину массива сумм совсем необязательно. Его можно формировать динамически просто добавляя очередную сумму элементов и попутно проверяя на уже наличие таковой (это отсеет немало лишних сумм и добавит драгоценные байты). В случае переполнения памяти ОС все равно ее кикнет, поэтому посчитать переполнение для установки n_max достаточно только 1 раз, гипотетически выделив (допустим 256 Mb = 256 * 1024 Kb = 256 * 1024 * 1024 = 268435456 byte ) памяти под массив сумм. С приведенной цифрой это при int = 4 массив сумм в 67108864 элементов, это массив чисел из 34 (35 уже больше) элементов в идеальном варианте, таком что суммы не равны между собой. короче я тут подсчитал вот:
массив сумм типа long long (у меня 8 байт) составляется из максимум 55 элементов массива, его длина 45148868444794 элемента. так что даже без факториалов главная задача длину массива сумм просто уложить в тип.

Добавлено через 7 часов 28 минут
я вот накидал. сыро, но работает добавляйте смотрите как будет лучше. очень рекомендую все таки формировать массив сумм динамически вместе с проверкой на уже имеющиеся там значения. Код не пример, при размере массива в 20 элементов можете оставлять компьютер и расслабиться с супругой или товарищами с беленькой, НО... можно неплохо его "довести".
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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
#include<iostream>
#include<fstream>
#include<stdlib.h>
 
#define SIZE_M  15
 
bool check_min_max(int min, int max);
 
int main(){
    int mass[SIZE_M];
 
    //init array
    for(int i = 0; i != SIZE_M; ++i)
        mass[i] = rand() % SIZE_M * 2 + 1;
 
    //opening ofstream
    const char *file = "file.txt";
    std::ofstream ofs(file);
 
    if(!ofs.is_open()){
        std::cerr << "error of open file " << file << "\n";
        return 1;
    }
 
    //printing sourse array
    ofs << "sourse array \n";
    for(int i = 0; i != SIZE_M; ++i)
        ofs << mass[i] << " ";
    ofs << std::endl << std::endl;
 
    //sorting array
    for(int i = 0; i != SIZE_M - 1; ++i)
        for(int k = i + 1; k < SIZE_M; ++k)
            if(check_min_max(mass[i], mass[k])){
                mass[k] += mass[i];
                mass[i] = mass[k] - mass[i];
                mass[k] -= mass[i];
            }
 
    //printing sorting array
    ofs << "sorting array \n";
    for(int i = 0; i != SIZE_M; ++i)
        ofs << mass[i] << " ";
    ofs << std::endl << std::endl;
 
    //creating sum_array
    long long *mass_summ, size_mass_summ = 1 << SIZE_M;
    mass_summ = new long long [size_mass_summ];
 
    for(int i = 0; i < size_mass_summ; ++i)
        mass_summ[i] = 0;
 
    int summ = 0;
 
    //puts the summ in summ_array
    for (int i = 0; i < size_mass_summ; ++i){
 
        int tmp = 0, k = i;
        bool check = true;
 
        while(k){
            if(k & 1){
                summ += mass[tmp];
                //ofs << mass[tmp] << ' ';
            }
            ++tmp;
            k = k >> 1;
        }
        //ofs << "\t";
        for(int k = i; k > 0; --k)
            if (mass_summ[k] == summ) check = false;
 
        if(check) mass_summ[i] = summ;
        summ = 0;
    }
 
    //sorting summ_array
    for(int i = 0; i != size_mass_summ - 1; ++i)
        for(int k = i + 1; k < size_mass_summ; ++k){
            if(check_min_max(mass_summ[i], mass_summ[k])){
                mass_summ[k] += mass_summ[i];
                mass_summ[i] = mass_summ[k] - mass_summ[i];
                mass_summ[k] -= mass_summ[i];
            }
        }
    //deleting elements of array who is 0
    /*int count = 0;
 
    for(int i = 0; i != size_mass_summ; ++i){
        if((mass_summ[i] && mass_summ[i + 1]) == 0)
            ++count;
        else break;
    }
    -- count;
 
    //if(count){
        long long *mass_tmp = new long long[size_mass_summ - count];
        int tmp = 0;
 
        for(int i = count; i != size_mass_summ; ++i){
            mass_tmp[tmp] = mass_summ[i]; ++tmp;
        }
        delete []mass_summ;
 
        size_mass_summ -= count;
        mass_summ = new long long[size_mass_summ];
 
        for(int i = 0; i != size_mass_summ; ++i)
            mass_summ[i] = mass_tmp[i];
 
        delete []mass_tmp;
 
 
    ofs << "\n deleted elements of array who is 0 is: " << count <<"\n\n";
    //printing summ_array
    ofs << "sorting summ_array \n";
    for(int i = 0; i != size_mass_summ; ++i){
        //if(!(i % 30)) ofs << "\0";
        ofs << mass_summ[i] << " ";
    }*/
    ofs << std::endl << std::endl;
 
    int iskomoe_chislo = 1;
 
    for(int i = 1; i != size_mass_summ; ++i){
        bool check = true;
 
        if(check) {
            if(mass_summ[i] - mass_summ[i - 1] > 1){
                iskomoe_chislo = mass_summ[i - 1] + 1;
                check = false;
                break;
            }
            else{
                iskomoe_chislo = 1;
                for (int i = 0; i != SIZE_M; ++i)
                    iskomoe_chislo += mass[i];
            }
        }
    }
 
    ofs << "\nsearching number: " << iskomoe_chislo << " YPA!!!\n";
 
    delete []mass_summ;
    return 0;
}
 
bool check_min_max(int min, int max){
    bool check = min > max ? true : false;
    return check;
}
результат
Код
$ ./tmp 
chertopolox@chertopolox-Ubuntu:~/documents/projects/tmp/bin/Release$ cat ~/documents/file.txt 
sourse array 
27 3 25 21 17 21 3 25 19 3 5 15 11 9 17 

sorting array 
3 3 3 5 9 11 15 17 17 19 21 21 25 25 27 

searching number: 1 YPA!!!
Mr.X
Эксперт С++
 Аватар для Mr.X
2807 / 1583 / 248
Регистрация: 03.05.2010
Сообщений: 3,688
21.09.2011, 08:21     мне нужна помощь по курсовой работе!!! #16
Цитата Сообщение от Thinker Посмотреть сообщение
Возможно, задача требует 2^n переборов.
Что-то, мне кажется, вы несколько в другую сторону пошли. Ведь у нас задача найти не все возможные суммы, а минимальную "дыру" в массиве. Если в массиве "дыр" нет, то искомое число X равно сумме всех элементов массива плюс один. Очевидно, что "дыра" в этом массиве появится только в том случае, если мы добавим к нему элемент, больший X. Собственно, в этом и идея решения из сообщения #3, и оно мне кажется похожим на правду.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
21.09.2011, 09:27     мне нужна помощь по курсовой работе!!! #17
Мое решение этой задачи:
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
#include <iostream>
#include <vector>
#include <algorithm>
 
int main()
{
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    
    int n;
    std::cin >> n;
    
    std::vector<int> arr(n);
    for (int i = 0; i < n; ++i)
        std::cin >> arr[i];
    
    std::sort( arr.begin(), arr.end() );
    
    __int64 sum = 0;
    
    for (size_t i = 0; i < arr.size() ; ++i)
        if (arr[i] <= sum + 1)
            sum += arr[i];
        else
            break;
    
    std::cout << sum + 1;
    
}
Быстрее вроде нельзя...
Работает за O(nlogn), точнее за сортировку и один проход по массиву(не всегда до конца).
P.S. В третьем посте то же самое, только там сложность http://www.cyberforum.ru/cgi-bin/latex.cgi?O({n}^{3}) из-за квадратичной сортировки.
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
21.09.2011, 12:32     мне нужна помощь по курсовой работе!!! #18
Цитата Сообщение от Mr.X Посмотреть сообщение
Что-то, мне кажется, вы несколько в другую сторону пошли.
Да, выспался что называется. Вы правы, с помощью математической индукции легко доказать, что алгоритм из поста 3 выдает правильное решение.
alkagolik
 Аватар для alkagolik
1510 / 616 / 79
Регистрация: 15.07.2011
Сообщений: 3,552
21.09.2011, 14:18     мне нужна помощь по курсовой работе!!! #19
тут была неправда
Да, вижу пост №3 пошел в правильном пути, только без сортировки массива
C++
1
2
3
4
5
int i = 0; chislo = 1;
 
while(chislo >= mass[i]){
      chislo += mass[i]; ++i;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.09.2011, 15:43     мне нужна помощь по курсовой работе!!!
Еще ссылки по теме:

Вопросы по курсовой работе C++
C++ Сделать блок-схему к курсовой работе (движения тела, брошенного под углом к горизонту)
C++ Нужна заставка для курсовой C++

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

Или воспользуйтесь поиском по форуму:
ruslan000
0 / 0 / 0
Регистрация: 19.09.2011
Сообщений: 9
21.09.2011, 15:43  [ТС]     мне нужна помощь по курсовой работе!!! #20
мой с++ выдайт ошибки на все решения, кроме того что я кинул
Yandex
Объявления
21.09.2011, 15:43     мне нужна помощь по курсовой работе!!!
Ответ Создать тему
Опции темы

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