Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.55/11: Рейтинг темы: голосов - 11, средняя оценка - 4.55
0 / 0 / 0
Регистрация: 19.09.2011
Сообщений: 9
1

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

19.09.2011, 22:18. Показов 2097. Ответов 19
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
(Делать нужно на С++)
Задание такое: Задан массив натуральных чисел P[n]. Найти минимальное натуральное число, не представимое суммой никаких элементов массива P. Сумма может состоять из одного слогаемого, но каждый элемент массива может входить в неё только 1 раз.

Добавлено через 1 час 51 минуту
а всё, кажись разобрался=)
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
19.09.2011, 22:18
Ответы с готовыми решениями:

Вопросы по курсовой работе
Привет всем. Создал эту тему, чтобы задавать вопросы по ходу дела. Что-то я ищу в Интернете, а...

Помогите с написанием программы по курсовой работе
Помогите с написанием программы по курсовой работе на тему:"Автоматизація обліку книг в публічній...

Нужна помощь по курсовой работе
нужна помощь по курсовой работе! кто-нибудь владеет wolfram?

Нужна помощь по курсовой работе. Матрицы.
Нужна помощь, по курсовой работе, матрицы 1. Найти наименьший, по абсолютной величине, элемент...

19
Заблокирован
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, но думаю что это пока не понадобится.
1
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 минуту
я тупо не знаю как оформить курсовую=)

 Комментарий модератора 
Используйте теги форматирования кода!
0
Заблокирован
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?
0
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
вообще это для упорядоченного массива, я не знаю как сделать для не упорядоченного.
0
1186 / 542 / 78
Регистрация: 01.07.2009
Сообщений: 3,517
20.09.2011, 16:37 6
Ну так отсортируй массив:
C++
1
2
3
4
#include <algorithm>
...
 
sort(a,a+n);
0
Заблокирован
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. Дальше виже так, что берется число, проверяется на принадлежность к массиву, если нет, то раскладывается в ряды и проверяется на наличие элементов рядов массиву.
0
Эксперт С++
4267 / 2241 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
20.09.2011, 18:02 8
Не то, удалено все.
0
Заблокирован
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;
}
0
Эксперт С++
4267 / 2241 / 203
Регистрация: 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.
0
Заблокирован
20.09.2011, 18:46 11
Thinker, и я об том. при массиве mass[n]; n = 4, m = {1, 2, 3, 4} и не забыть отсортировать массив сумм
0
Эксперт С++
4267 / 2241 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
20.09.2011, 19:00 12
Цитата Сообщение от alkagolik Посмотреть сообщение
короче задача разобрана по косточкам.
Да, но если в массиве n=1000 элементов, то для массива сумм понадобится 2^1000 элементов.
Нужны уточнения на ограничения параметра n. При большом n массив сумм ни в какие ворота (то есть память) не влезет

Очень кажется, что на исходный массив ограничения должны быть наложены, иначе сложность алгоритма ОЧЕНЬ высокая, да и памяти надо МНОГО.
0
Заблокирован
20.09.2011, 19:01 13
Thinker, не нужно уточнений. курсовик нормальный (серьезный если можно так сказать). На применение длинной арифметики и вычисление факториалов через string. Ну а фактически надо исходить конечно из памяти. Ведь на диске с любой программой, игрой всегда пишется сколько ей нужно ОП для корректной работы. Т.е. вычислить при каком "n - размерность массива" программа просто уложится в объем ОП. Или менять алгоритм в корне.
0
Эксперт С++
4267 / 2241 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
20.09.2011, 19:06 14
Цитата Сообщение от alkagolik Посмотреть сообщение
Thinker, не нужно уточнений...
Пусть так. Если более оптимальных алгоритмов нет для такой задачи, тогда курсовая работа и правда хорошая
0
Заблокирован
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!!!
0
Эксперт С++
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
21.09.2011, 08:21 16
Цитата Сообщение от Thinker Посмотреть сообщение
Возможно, задача требует 2^n переборов.
Что-то, мне кажется, вы несколько в другую сторону пошли. Ведь у нас задача найти не все возможные суммы, а минимальную "дыру" в массиве. Если в массиве "дыр" нет, то искомое число X равно сумме всех элементов массива плюс один. Очевидно, что "дыра" в этом массиве появится только в том случае, если мы добавим к нему элемент, больший X. Собственно, в этом и идея решения из сообщения #3, и оно мне кажется похожим на правду.
2
Higher
1953 / 1219 / 120
Регистрация: 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. В третьем посте то же самое, только там сложность https://www.cyberforum.ru/cgi-bin/latex.cgi?O({n}^{3}) из-за квадратичной сортировки.
0
Эксперт С++
4267 / 2241 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
21.09.2011, 12:32 18
Цитата Сообщение от Mr.X Посмотреть сообщение
Что-то, мне кажется, вы несколько в другую сторону пошли.
Да, выспался что называется. Вы правы, с помощью математической индукции легко доказать, что алгоритм из поста 3 выдает правильное решение.
0
Заблокирован
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;
}
0
0 / 0 / 0
Регистрация: 19.09.2011
Сообщений: 9
21.09.2011, 15:43  [ТС] 20
мой с++ выдайт ошибки на все решения, кроме того что я кинул
0
21.09.2011, 15:43
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
21.09.2011, 15:43
Помогаю со студенческими работами здесь

Мне очень срочно нужна помощь в работе с файлом.
Народ здрасте! Проблема такая. Я ввожу текст в файл (ну типа в .txt) вот так: FileInfo file =...

Нужна помощь с курсовой работой.
Будьте добры помогите пожалуйста. Вообще задали курсовой проект по моделированию UML. 2....

Мне нужна помощь
Памагітє пажаласта мнє нада написать праграму метада Ейлера ...? Переводы: NiTan (прямой):...

Нужна помощь по работе с usb
Нужна помощь по работе с usb. Пишу программу для сот. телефона.


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru