|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
10.08.2011, 11:47 | #1 |
Пользователь
Регистрация: 10.08.2011
Сообщений: 10
|
Сравнение последовательности чисел с часть самой себя
Здравствуйте. Есть небольшая задача. Правда я был студентом настолько давно, что уже практически позабыл все в алгоритмизации и программировании. Поэтому, прошу сразу тему не закрывать из-за отсутствия строчки кода.
Конкретно по теме: есть достаточно длинная последовательность чисел, нужно взять любую ее часть и провести сравнение для нахождения наиболее похожей части во всей последовательности. Идеи: Можно записать последовательность в текстовый файл и загрузить ее как одномерный массив. После взять массив размера k с элементами от i до i+k, сравнить элементы массива, вывести наиболее похожую последовательность(примерно k или k+10 элементов) в файл. 1. Узнать сколько элементов последовательности в файле – это будет размер массива А. 2. Произвести сравнение короткой последовательности с первыми k элементами, если процент меньше конкретного значения, то начать сравнение, но уже не с первого элемента, а с увеличенного на 1. 3. Во время сравнения, нужно чтобы сравнивало не один к одному элементы, а данный элемент массива В с 2-мя – 3-мя элементами массива А. То есть берем элемент B[1] сравниваем с элементом A[1], если результат true, то записываем в третий массив, если нет, то сравниваем B[1] с A[2], ну и с третьим. После чего если есть такое же число, то пишем в массив С и переходим на следующий элемент массива B, иначе просто переходим на следующий элемент массива B. |
10.08.2011, 14:27 | #2 |
Старожил
Регистрация: 03.01.2011
Сообщений: 2,508
|
алгоритм так смутно описан, что на ум приходят нейронные сети )
Основной вопрос, это критерий "похожести". Если есть исходная последовательность [1, 2, 3], то какой вариант будет наиболее всего на неё похож? [1, 3, 3] [2, 2, 3] [1, 2, 2] [1, 4, 2, 3] Не отвлекайтесь на текстовые файлы и прочие абсолютно несущесвенные мелочи реализации, опишите чётко и однозначно алгоритм, тогда может кто-то и сможет помочь.
"Когда приходит положенное время, человек перестаёт играть в пинбол. Только и всего."
|
10.08.2011, 14:32 | #3 |
Пользователь
Регистрация: 10.08.2011
Сообщений: 10
|
Правильный ответ [1,4,2,3]
|
10.08.2011, 15:59 | #4 | |
Старожил
Регистрация: 20.04.2008
Сообщений: 5,526
|
Цитата:
В похожей должна содержаться вся исходная последовательность (12,3) и некоторые лишние (4) в произвольных местах. Задача найти с наименьшим числом дополнительных.
программа — запись алгоритма на языке понятном транслятору
|
|
10.08.2011, 16:08 | #5 |
Пользователь
Регистрация: 10.08.2011
Сообщений: 10
|
Даже очень правильно, только, последовательность может быть и без лишних элементов.
|
10.08.2011, 18:26 | #6 |
В стагнации
Участник клуба
Регистрация: 29.07.2011
Сообщений: 1,303
|
А последовательность [2,1,3] отличается от [1,2,3]?
E-mail: pashaworking@gmail.com | ICQ: 479914426 | Skype: moondearr
Понять, чего от тебя требует заказчик – это уже половина всей работы, а иногда и полностью выполненное задание. |
11.08.2011, 09:17 | #7 |
Пользователь
Регистрация: 10.08.2011
Сообщений: 10
|
Это совсем другая последовательность. Главный критерий схожести - это присутствие всех элементов последовательности, в той же последовательности с присутствием некоторого мусора. Правильным ответом будет даже [1,2,2,3], только вторая 2 будет уже мусором, так как первую мы запишем как совпадение с проверяемым элементом, и начнем проверку на совпадение 3.
|
11.08.2011, 09:26 | #8 | |||
Старожил
Регистрация: 20.04.2008
Сообщений: 5,526
|
Цитата:
Цитата:
пойдем дальше. Размеры последовательностей исходной, искомой, максимальное число добавлений при которых последовательности еще будут считаться похожими? (ориентировочные размеры) например 10000/100/10 (в последовательности из 10000 элементов ищем 100 элементов с не болле чем 10 добавлениями). Искать все подходящие или достаточно ограничится первым. Цитата:
(10. 2) длины 10 с 2 добавлениями. (12, 4) ? и почему так.
программа — запись алгоритма на языке понятном транслятору
|
|||
11.08.2011, 09:51 | #9 |
Пользователь
Регистрация: 10.08.2011
Сообщений: 10
|
Достаточно найти первую, а не лучшую. И суть не важно, сколько в ней всего добавлений, важней поставить критерий, чтобы было не более чем 2 между двумя элементами последовательности.
|
11.08.2011, 13:12 | #10 | ||
Старожил
Регистрация: 20.04.2008
Сообщений: 5,526
|
Цитата:
все остальные условия соблюдены Цитата:
или вообще достаточно длины 2?!
программа — запись алгоритма на языке понятном транслятору
|
||
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
С\С++ Дана последовательность чисел. Найти количество различных чисел в этой последовательности | yuliyayuliya | Помощь студентам | 1 | 14.04.2011 06:30 |
Сравнение двух листов и вывод в определённой последовательности | ОlGa | Microsoft Office Excel | 1 | 29.01.2010 21:06 |
Определить k-ую цифру последовательности Фибоначчи и последовательности натуральных чисел. | Med | Помощь студентам | 1 | 20.03.2009 11:40 |
обмен чисел последовательности | maziLa | Паскаль, Turbo Pascal, PascalABC.NET | 2 | 09.12.2008 00:15 |
вычисление суммы чисел, кратных 3 из последовательности, состоящей из 10 чисел, заранее заданных | Белка | Помощь студентам | 3 | 27.10.2007 11:53 |