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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.92
ruslan000
0 / 0 / 0
Регистрация: 19.09.2011
Сообщений: 9
#1

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

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

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

Добавлено через 1 час 51 минуту
а всё, кажись разобрался=)
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.09.2011, 22:18
Здравствуйте! Я подобрал для вас темы с ответами на вопрос мне нужна помощь по курсовой работе!!! (C++):

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

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

Нужна тема для курсовой - C++
Доброго времени суток! Если не сложно , подкиньте пару тем для курсовой Желательно чтобы была связь с API Вконтакте. Заранее...

Нужна заставка для курсовой C++ - C++
код какой-либо заставки для курсовой с надо

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

Помощь при работе с функциями в Си++ - C++
Как правильно обратится к элементам массива в функции zam int zam(int n, int m, int**a) { int tmp; for(int i=0; i<n; i++) ...

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

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

Очень кажется, что на исходный массив ограничения должны быть наложены, иначе сложность алгоритма ОЧЕНЬ высокая, да и памяти надо МНОГО.
0
alkagolik
Заблокирован
20.09.2011, 19:01 #13
Thinker, не нужно уточнений. курсовик нормальный (серьезный если можно так сказать). На применение длинной арифметики и вычисление факториалов через string. Ну а фактически надо исходить конечно из памяти. Ведь на диске с любой программой, игрой всегда пишется сколько ей нужно ОП для корректной работы. Т.е. вычислить при каком "n - размерность массива" программа просто уложится в объем ОП. Или менять алгоритм в корне.
0
Thinker
Эксперт С++
4227 / 2201 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
20.09.2011, 19:06 #14
Цитата Сообщение от alkagolik Посмотреть сообщение
Thinker, не нужно уточнений...
Пусть так. Если более оптимальных алгоритмов нет для такой задачи, тогда курсовая работа и правда хорошая
0
alkagolik
Заблокирован
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
21.09.2011, 04:11
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.09.2011, 04:11
Привет! Вот еще темы с ответами:

Нужна помощь Строки. - C++
Составить программу вывода последовательности символов ZYYXXX...AA..AA Y на экран.

Нужна помощь с ассемблером. - C++
Пыталась сама написать, да что-то не очень у меня получается. Задание состоит в том, чтобы найти минимальное положительное число в...

Нужна помощь с программой - C++
Добрый день!! Помогите пожалуйста с программой, задача состоит в следующем: Все задания выполняются с использованием классов. ...

Нужна помощь с программой - C++
ПРограмма должна выполнять расчет коэффициентов характеристического полинома квадратной матрицы


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

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

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