|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
12.10.2009, 18:23 | #1 |
Пользователь
Регистрация: 20.09.2009
Сообщений: 33
|
Шифр
Вобщем надо построить массив из n количества чисел(n вводит пользователь)... но так, чтобы каждое число повторялось 3 раза или кратное 3м число раз... НО одно число встречается некратное трём число раз... Надо найти это число
|
12.10.2009, 18:42 | #2 |
Форумчанин
Регистрация: 10.10.2009
Сообщений: 680
|
какие ограничения на n? При детских очень простая сортировочная или переборная задача, при больших - задача олимпиадного уровня, решение которой в случае, если неизвесно какое количество раз встречается искомое число, мне неизвесно.
|
12.10.2009, 18:43 | #3 |
Форумчанин
Регистрация: 10.10.2009
Сообщений: 680
|
И еще кое-что, я не понял, что от нас требуется? написать и шифровщик, и дешифровщик? а то сначала зашифровать, а во второй части задания - розшифровать
|
12.10.2009, 19:06 | #4 |
Пользователь
Регистрация: 20.09.2009
Сообщений: 33
|
1<=N<=300001... ну в задаче написано так. цитирую:"среди большого количества чисел спрятано секретное число, причем все числа встречаются трижды(или кратное трём число раз), кроме секретного числа, которое встречается некратное трём число раз" ...надо найти сектретное число
|
12.10.2009, 19:13 | #5 |
Форумчанин
Регистрация: 10.10.2009
Сообщений: 680
|
300000? Тогда это довольно простая задача. Сложно, если, к примеру, большое ограничение по времени и маленькое по памяти, и чисел много (пример - решал для 2кратного повторения, 60 секунд, 1 число без пары вообще 2мб памяти и 100млн чисел, и для 3кратного, 60секунд, 1 число без пары вообще, 2 мб памяти, 50млн чисел).
Сдесь просто пишем быструю сортировку, а потом линейным алгоритмом обходим массив, который получится, и на ходу занимаемся поиском нужного числа. Даже при кривом кусорте должно работать примерно 0.8-0.9 секунды. |
12.10.2009, 19:16 | #6 |
Пользователь
Регистрация: 20.09.2009
Сообщений: 33
|
я конечно понимаю что форум для профессионалов, но я новичок... поэтому можно хотябы некоторые элементы кода для решения этой задачи?
|
12.10.2009, 19:30 | #7 |
Форумчанин
Регистрация: 10.10.2009
Сообщений: 680
|
Я пока далеко не профессионал Как пишется быстрая сортирока - гугл в помощь.
По поводу элементов - проверять после сориторовки надо так Код:
1 1 1 2 2 2 5 5 5 12 12 12 18 18 122 122 122 - то когда дойдем до 122 - будет обрыв группы длиной, отличной от 3 (группа 18 18), поэтому ответом станет 18). нм - текущая длина группы одинаковых. Дальше думаю сами разберетесь. НУ еще объясню, что сначала первый сразу заливаю в группу длиной 1 (ведь перед ним нету других элементов), и просматриваю со второго. |
12.10.2009, 19:32 | #8 |
Форумчанин
Регистрация: 10.10.2009
Сообщений: 680
|
Еще одно хочу добавить - если дойдем до последнего элемента, а ответа не будет, то ответ - текущее значение nm (просто мы не увидели обрыва, так как группа последняя, ответом является самое большое число массива, обрыв - конец этого массива).
|
12.10.2009, 19:37 | #9 |
Пользователь
Регистрация: 20.09.2009
Сообщений: 33
|
Числа идут не по порядку
|
12.10.2009, 19:51 | #10 |
Форумчанин
Регистрация: 10.10.2009
Сообщений: 680
|
Для невнимательных повторяю еще раз - сначала быстрая сортировка, потом линейный обход.
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Шифр Бекона | А. Долматов | Общие вопросы Delphi | 3 | 22.04.2012 04:45 |
Шифр Хилла | Fallen Soul | Помощь студентам | 4 | 05.10.2009 02:09 |
че за шифр? | Анастасия123456789 | Помощь студентам | 4 | 11.05.2009 19:19 |
Разгадайте шифр | П@fнутич:-) | Свободное общение | 56 | 12.04.2009 22:28 |
Шифр | Razora | Свободное общение | 10 | 26.06.2007 15:52 |