0 / 0 / 0
Регистрация: 19.09.2011
Сообщений: 9
|
|
1 | |
мне нужна помощь по курсовой работе!!!19.09.2011, 22:18. Показов 2097. Ответов 19
Метки нет (Все метки)
(Делать нужно на С++)
Задание такое: Задан массив натуральных чисел P[n]. Найти минимальное натуральное число, не представимое суммой никаких элементов массива P. Сумма может состоять из одного слогаемого, но каждый элемент массива может входить в неё только 1 раз. Добавлено через 1 час 51 минуту а всё, кажись разобрался=)
0
|
19.09.2011, 22:18 | |
Ответы с готовыми решениями:
19
Вопросы по курсовой работе Помогите с написанием программы по курсовой работе Нужна помощь по курсовой работе Нужна помощь по курсовой работе. Матрицы. |
Заблокирован
|
||||||
19.09.2011, 22:45 | 2 | |||||
вычисляем минимальное число типа int (в разных архитектурах разные длины типов поэтому для переносимости кода ее надо именно вычислить)
Конечно легче узнать минимальное значение средствами STL, но думаю что это пока не понадобится.
1
|
0 / 0 / 0
Регистрация: 19.09.2011
Сообщений: 9
|
||||||||||||
19.09.2011, 22:48 [ТС] | 3 | |||||||||||
я тупо не знаю как оформить курсовую=)
0
|
Заблокирован
|
||||||
19.09.2011, 23:57 | 4 | |||||
не правда ли так более приятно читать код?
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 Последнее 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 | |||||
Ну так отсортируй массив:
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
|
Заблокирован
|
|||||||||||
20.09.2011, 18:37 | 9 | ||||||||||
и в довершение Thinker, покажу "на пальцах". Дан массив mass[4] = {1, 3, 5, 8}. Вспоминая комбинаторику создаем массив для сумм всех сочетаний без повторений в данном случае 15. Заполняем его суммами сочетаний без повторений, т.е. n = 4, m = {1, 2, 3, 4}
ищем разницу mass_summ[i + 1] - mass_summ[i] >1, если да то... пока еще не придумал иначе max(mass_summ[i]) + 1 короче задача разобрана по косточкам. Отсортировать массив можно как бы так:
0
|
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, 19:00 | 12 |
Да, но если в массиве n=1000 элементов, то для массива сумм понадобится 2^1000 элементов.
Нужны уточнения на ограничения параметра n. При большом n массив сумм ни в какие ворота (то есть память) не влезет Очень кажется, что на исходный массив ограничения должны быть наложены, иначе сложность алгоритма ОЧЕНЬ высокая, да и памяти надо МНОГО.
0
|
Заблокирован
|
|
20.09.2011, 19:01 | 13 |
Thinker, не нужно уточнений. курсовик нормальный (серьезный если можно так сказать). На применение длинной арифметики и вычисление факториалов через string. Ну а фактически надо исходить конечно из памяти. Ведь на диске с любой программой, игрой всегда пишется сколько ей нужно ОП для корректной работы. Т.е. вычислить при каком "n - размерность массива" программа просто уложится в объем ОП. Или менять алгоритм в корне.
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 элементов можете оставлять компьютер и расслабиться с супругой или товарищами с беленькой, НО... можно неплохо его "довести".
результат
Код
$ ./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 |
Что-то, мне кажется, вы несколько в другую сторону пошли. Ведь у нас задача найти не все возможные суммы, а минимальную "дыру" в массиве. Если в массиве "дыр" нет, то искомое число X равно сумме всех элементов массива плюс один. Очевидно, что "дыра" в этом массиве появится только в том случае, если мы добавим к нему элемент, больший X. Собственно, в этом и идея решения из сообщения #3, и оно мне кажется похожим на правду.
2
|
Higher
|
||||||
21.09.2011, 09:27 | 17 | |||||
Мое решение этой задачи:
Работает за O(nlogn), точнее за сортировку и один проход по массиву(не всегда до конца). P.S. В третьем посте то же самое, только там сложность из-за квадратичной сортировки.
0
|
0 / 0 / 0
Регистрация: 19.09.2011
Сообщений: 9
|
|
21.09.2011, 15:43 [ТС] | 20 |
мой с++ выдайт ошибки на все решения, кроме того что я кинул
0
|
21.09.2011, 15:43 | |
21.09.2011, 15:43 | |
Помогаю со студенческими работами здесь
20
Мне очень срочно нужна помощь в работе с файлом. Нужна помощь с курсовой работой. Мне нужна помощь Нужна помощь по работе с usb Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |