0 / 0 / 0
Регистрация: 03.07.2015
Сообщений: 1
|
|
1 | |
помогите написать лабу08.09.2009, 15:51. Показов 2715. Ответов 18
Метки нет (Все метки)
1. Дано 36-ричное число, содержащее не более 100 цифр (цифры 10,11,...,35 кодируются заглавными латинскими буквами А,В,...,Z). Переставить цифры числа таким образом, чтобы оно стало "счастливым". "Счастливым" будем называть число из N цифр, у которого сумма первых [N/2] цифр равна сумме последних [N/2] цифр. Если такая перестановка невозможна, вывести сообщение "impossible"
0
|
08.09.2009, 15:51 | |
Ответы с готовыми решениями:
18
Помогите решить лабу. Помогите решить лабу [2] Помогите, умоляю..... нужно сдать лабу..... срочно.... а нифига не получается.... я девушка, сразу поясняю..) Помогите написать лабу!! |
7175 / 3234 / 81
Регистрация: 17.06.2009
Сообщений: 14,164
|
|
09.09.2009, 13:46 | 2 |
Посчитать сумму цифр - SUM.
Если SUM нечетное, то сразу ответ - невозможно. Цифры отсортировать по убыванию. Потом перебор 2**N вариантов - нужно выбрать несколько цифр, чтобы их сумма была SUM/2. Тогда остальные невыбранные цифры в сумме тоже будут давать SUM/2. Останется только переставить цифры как требуется.
0
|
быдлокодер
1724 / 911 / 106
Регистрация: 04.06.2008
Сообщений: 5,679
|
|
09.09.2009, 14:40 | 3 |
Ответ будет таким же, если N тоже нечётное.
Неправильно. Выбирать нужно не несколько цифр, а N/2, не больше, не меньше. Поэтому сортировка бессмысленна. Просто перебор ряда неотсротированных цифр. Задача проста, но... рекурсия. Я попробовал было без рекурсии сделать с десятью значениями, и то плюнул, а тут сто. В данном случае размер кода определяет его сложность.
0
|
7175 / 3234 / 81
Регистрация: 17.06.2009
Сообщений: 14,164
|
|
09.09.2009, 14:53 | 4 |
В случае сортированных значений можно сократить перебор. То есть раньше найти нужный вариант.
0
|
14 / 14 / 2
Регистрация: 01.02.2009
Сообщений: 23
|
|
09.09.2009, 15:18 | 5 |
Тут пример есть этой задачи. Я утром пытался сделать но так и не получилось...
http://www.kursovik.com/programming/101003.html
0
|
быдлокодер
1724 / 911 / 106
Регистрация: 04.06.2008
Сообщений: 5,679
|
|
09.09.2009, 15:36 | 6 |
Ладно, давайте так.
Имеем ряд чисел. Допустим, их 10 x0, x1, x2, x3, x4, x5, x6, x7, x8, x9 Согласны вы со мной в том, что чтобы найти правильное решение, необходимо будет перебрать такие значения x0, x1, x2, x3, x4, x5, x6, x7, x8, x9 x0, x1, x2, x3, x4, x5, x6, x7, x8, x9 x0, x1, x2, x3, x4, x5, x6, x7, x8, x9 x0, x1, x2, x3, x4, x5, x6, x7, x8, x9 x0, x1, x2, x3, x4, x5, x6, x7, x8, x9 x0, x1, x2, x3, x4, x5, x6, x7, x8, x9 x0, x1, x2, x3, x4, x5, x6, x7, x8, x9 x0, x1, x2, x3, x4, x5, x6, x7, x8, x9 x0, x1, x2, x3, x4, x5, x6, x7, x8, x9 x0, x1, x2, x3, x4, x5, x6, x7, x8, x9 x0, x1, x2, x3, x4, x5, x6, x7, x8, x9 x0, x1, x2, x3, x4, x5, x6, x7, x8, x9 x0, x1, x2, x3, x4, x5, x6, x7, x8, x9 x0, x1, x2, x3, x4, x5, x6, x7, x8, x9 x0, x1, x2, x3, x4, x5, x6, x7, x8, x9 x0, x1, x2, x3, x4, x5, x6, x7, x8, x9 ...Это далеко не конец. И так далее. То есть, перебрать ВСЕ пятёрки? Рискну предположить, что согласны. И сразу: если это так, до для того, чтобы найти все решения задачи, придётся рассмотреть все пятёрки чисел, что в отсортированном, что в неотсортированном массиве. А вот если необходимо будет найти одно решение, то в самомо общем случае с отсортированном массивом работы будет больше. Ибо сперва будут рассматриваться первых 5 чисел.А их сумма больше последующих пяти безусловно- массив-то отсортиован. То есть где-то если решение сущесвует, где-то в середине такого вот перебора вы его найдёте. А может, и в конце. А в неотсортированном на правильное решение можно натолкнуться когда угодно. Но это был вопрос по сортировке. А теперь: ...Вы по-прежнему не хотите использовать рекурсию? Можно, кто же спорит...Но соловья баснями не кормят. Я дам вариант с рекурсией. Что касается варианта без рекурсии, то в исходнике должно быть 50 циклов, вложенных один в другой. Далее, не факт, что чисел-то будет 100! А это значит, что сумма N/2 чисел может подсчитываться не в теле самого последннего, внутреннего цикла, но и в телах остальных 49 циклов... И всё это надо описать... Нет, уж увольте. Или я не прав?
0
|
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
|
09.09.2009, 20:16 | 7 |
Если еще совсем не опоздал то ответьте. Я могу написать необходимую Вам программу.
0
|
0 / 0 / 0
Регистрация: 03.07.2015
Сообщений: 1
|
|
10.09.2009, 16:12 | 8 |
нет, не опоздал!!я только за!!))
0
|
7175 / 3234 / 81
Регистрация: 17.06.2009
Сообщений: 14,164
|
|
10.09.2009, 17:02 | 9 |
Полный перебор - это то чего хочешь сделать ты. Но есть разные методы сократить полный перебор. В частности если отсортировать массив, что можно сократить число вариантов. Пусть например x0==100, x1==100, а остальные xi сильно меньше. Тогда при переборе все варианты когда выбрано и x0 и x1 не годятся для решения. В частности все варианты которые ты написал в посте вообще не следует перебирать Единственная здравая мысль
0
|
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
||||||
10.09.2009, 19:27 | 10 | |||||
Ну вот вроде бы все:
0
|
1 / 1 / 1
Регистрация: 29.08.2009
Сообщений: 63
|
|
11.09.2009, 18:00 | 11 |
сыпется твой алгоритм на 111342
Добавлено через 5 минут полный перебор практически сразу отпадает 100! переставновок завесят любой комп стоит или нет использовать рекурсию лучше обсудить когда появится приемлимый по времени выполнения алгоритм данная задача задавалась в учебнике ахо ульмана алгоритмы и структуры данных, с максимальным рейтингом сложности, может стоит где поискать ответы с подсказками решений?
0
|
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
||||||
12.09.2009, 16:38 | 12 | |||||
_mayor,
Каюсь, писал после 2-х л пива, а накануне был 1 л водки. Теперь написал на трезвую голову. Проверял работает и с числами под 100 цифр.
0
|
быдлокодер
1724 / 911 / 106
Регистрация: 04.06.2008
Сообщений: 5,679
|
|||||||||||||||||||||
13.09.2009, 05:40 | 13 | ||||||||||||||||||||
Естественно.
...Тем не менее, других алгоритмов я не вижу. А некоторые остряки штатские видят, но молчат с умным видом. Дескать, знаем, но не скажем. Пусть реализую формулировку "остальные xi сильно меньше". (odipовский перл) тогда и будем говорить. Но слоловья баснями не кормят. Короче, вот моё НЕПОЛНОЕ решение с рекурсией.
Как- это пусть тредстартер думает. Далее, если чисел нечётное число или их сумма нечётна, написать, что решения нет. Теперь нужно прописать количество чисел. Это может сделать программно, подсчитав их, можно вручную. В моём примере это сделано в макросе
Для тредстартерского примера его начальное значение равно kolichestvo_chisel/2 То есть половина будет. Если чисел 40, то половина будет 20. Эта функция выдаёт на гора все суммы пятёрок, шестёрок- двадцаток и так далее, кто что пожелает. Задача тредтстартера ВРУЧНУЮ найти половину (SUM) суммы и каждый раз сравнивать выведенную сумму с SUM. Предварительно сохранив номера элементов массива stroka. Допустим, однажды суммы сравнялись. Ага, номера известны. Теперь заполняй новый массив последвательно элементами с такими нормеами, и потом с оставшимися номерами. Это всё автор пусть сам делает. ...Ну, а моя функция работает так. Каждый раз в функции рассматривается ПОДМАССИВ последовательно идущих чисел и ищется его сумма. Допустим, массив чисел такой 12, 34, 56, 67, 34, 56, 100, 12, 45, 100, 23, а подмассив такой 12, 34, 56, 67, 34, 56, 100, 12, С помощью нехитрых манипуляций вызывается рекурсивно эта же функция, работающая уже с таким подмассивом 34, 56, 67, 34, 56, 100, 12, потом с таким 56, 67, 34, 56, 100, 12, и так далее, пока не останется число 12. Теперь к сумме последовательно прибавляется и отнимается число 12, потом 45, 100 и 23 Следующий расассматриваемый подмассив будет (благодаря циклу) 100, 12 Вот так по функциям проходим и ищем сумму. Ну, там ещё каждый раз функция принимает служебные аргументы- номер функции, номер элемента (имеется ввиду индекс в stroka) и сколько элементво осталось прибавить. Автор, вопрос на соображение. И всем тоже. Значит, задача поставлена, условие известно. Если решение есть (что не факт), я могу со стопроцентной вероятностью указать одно его число. Не примерно, не скорее всего, а именно 100 процентов, что это число (шестнадцатиричная цифра) будет присутствовать в ответе. Какое это число? Ну, всё, пока. P. S. Предыдущий алгоритм представлял бы интерес с комментариями какими-нибудь, что ли...
0
|
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
|
13.09.2009, 08:07 | 14 |
Комментарии к предыдущему алгоритму:
1. Заносим значения каждой цифры введеного числа в массив mas_ch[] в десятичной форме (для этого используем созданный массив mas_36[]). 2. Проводим (проверку на то что количество цифр четное и что сумма цифр делится без остатка на 2). 3. Вычисляем сумму элементов (она нам нужна , т.к. в дальнейшем алгоритм построен таким образом: необходимо выбрать половину цифр, чтобы их сумма была равна половине суммы). 4. С помощью стека делаем перебор элементов (стек создан размером = половина количества цифр начального числа).(В дальнейшем я пишу "сумма цифр в стеке", это для простоты. На самом деле в стеке находятся индексы элементов массива mas_ch[] и я подразумеваю под суммой цифр в стеке - сумму элементов массива mas_ch[] индексы которых находятся в стеке) В общих чертах перебор выглядит так (перебор выполняем до тех пор пока первым элементом в стеке не окажется индекс цифры массива mas_ch[]) который = половина количества цифр массива mas_ch[] + 1): Заносим число в стек. Входим в цикл. Первая проверка: если стек заполнен и сумма цифр стека равна половине суммы цифр массива mas_ch[], то выходим из цикла. Вторая проверка: если в стеке последний индекс массива mas_ch[] и сумма цифр стека не равна половине суммы цифр массива mas_ch[], то удаляем из стека подряд идущие индексы, затем еще один и вместо последнего в стек заносим следующий за ним. (При первом прохождении цикла эта проверка не нужна, но нужна при последующих прохождениях). Третья проверка: ((если стек заполнен, а сумма цифр стека не равна половине суммы цифр массива mas_ch[]) или (стек не заполнен, а сумма превышена)) и не достигнут последний индекс массива mas_ch[], то последний индекс массива mas_ch[] в стеке заменяем на следующий. Четвертая проверка: если стек не заполнен и сумма цифр стека не превышает половины суммы цифр массива mas_ch[], то заносим в стек следующий индекс массива mas_ch[]. В конце цикла нахожу сумму цифр стека. После цикла еще одна проверка на счастливость и вывод результата (с переводом десятичных чисел в 36-ричные).
0
|
7175 / 3234 / 81
Регистрация: 17.06.2009
Сообщений: 14,164
|
|
13.09.2009, 10:19 | 15 |
0
|
быдлокодер
1724 / 911 / 106
Регистрация: 04.06.2008
Сообщений: 5,679
|
|
13.09.2009, 12:55 | 16 |
valeriikozlov, переменная LIFO что означает?
0
|
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
|
13.09.2009, 13:09 | 17 |
Переменная LIFO (массив) является стеком
0
|
evlan
|
|
18.09.2009, 15:20 | 18 |
Что будет если я введу 100 символов или больше? Правильно, переполнение буфера.
|
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
|
18.09.2009, 17:14 | 19 |
evlan,
А вы внимательно прочитайте условие задачи. Кстати я в начале задачи поставил проверку на не превышение 100 символов, так что ввести 100 символов и более Вам не удастся.
0
|
18.09.2009, 17:14 | |
18.09.2009, 17:14 | |
Помогаю со студенческими работами здесь
19
ПОМОГИТЕ СДЕЛАТЬ ЛАБУ Помогите сделать лабу на тему простые разветвления Не могу написать лабу, пожаалуйста!!! Помогите написать формулу ,никак немогу написать (2k)! в ней Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |