ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Найти позицию кратчайшей последовательность в списке A в котором встречаются все значения
20 сообщений из 45, страница 2 из 2
  2  все
Найти позицию кратчайшей последовательность в списке A в котором встречаются все значения
    #37306615
dubov1994
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
dubov1994
Гость
Вот те на,

хотя бы в том, что у вас countchecked никогда не обнуляется. да и в целом алгоритм неверен.
...
Рейтинг: 0 / 0
13.06.2011, 15:38
| Ответить | Цитировать | Написать  
Найти позицию кратчайшей последовательность в списке A в котором встречаются все значения
    #37306619
dubov1994
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
dubov1994
Гость
AndreTM,

а, вот думал же в 5 утра, что что-то забыл :-) одинаковые быстро фиксятся в моём алгоритме.
вообще, конечно, без ограничений ничего не сделать.
...
Рейтинг: 0 / 0
13.06.2011, 15:41
| Ответить | Цитировать | Написать  
Найти позицию кратчайшей последовательность в списке A в котором встречаются все значения
    #37306620
Фотография Вот те на
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Вот те на
Участник
dubov1994,

Он и не должен обнуляться.
...
Рейтинг: 0 / 0
13.06.2011, 15:42
| Ответить | Цитировать | Написать  
Найти позицию кратчайшей последовательность в списке A в котором встречаются все значения
    #37306623
dubov1994
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
dubov1994
Гость
Вот те на,

короче, найдите контрпримеры сами.
...
Рейтинг: 0 / 0
13.06.2011, 15:43
| Ответить | Цитировать | Написать  
Найти позицию кратчайшей последовательность в списке A в котором встречаются все значения
    #37306651
xaoc2
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
xaoc2
Гость
AndreTM,

AndreTM,
Список B не содержит повторяющихся значений
Используемые значения могут быть очень велики
...
Рейтинг: 0 / 0
13.06.2011, 16:04
| Ответить | Цитировать | Написать  
Найти позицию кратчайшей последовательность в списке A в котором встречаются все значения
    #37306655
Фотография Вот те на
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Вот те на
Участник
Вот веселые картинки к алгоритму.
...
Рейтинг: 0 / 0
13.06.2011, 16:10
| Ответить | Цитировать | Написать  
Найти позицию кратчайшей последовательность в списке A в котором встречаются все значения
    #37306664
Фотография ZyK_BotaN
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ZyK_BotaN
Участник
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
let a = [ 1 ; 2 ; 3 ; 4 ; 5 ; 3 ; 2 ; 4 ; 8 ; 5 ]
let b = [ 5 ; 2 ; 3 ]

let windowed = seq {
                    for i in b.Length .. a.Length do
                        yield! 
                            Seq.zip (Seq.windowed i a)
                                    [ 0 ..(a.Length-i)]
                   }
let pred (els, i) =
    b |> Seq.forall
            (fun x -> Seq.exists 
                        (fun el -> el = x)
                        els)

let result = 
    let (_, idx) = Seq.find pred windowed
    idx

обработку ситуации когда ответа нет, не делал
...
Рейтинг: 0 / 0
13.06.2011, 16:19
| Ответить | Цитировать | Написать  
Найти позицию кратчайшей последовательность в списке A в котором встречаются все значения
    #37306676
Фотография AndreTM
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AndreTM
Участник
xaoc2Используемые значения могут быть очень велики
Вот и вопрос - насколько велики? Вернее, разрядность значений какова?
Просто возникла мысль вместо перебора эначений множества B использовать, например, решето.
Скажем, при целых значениях, - гига оперативки хватит на числа (порядка) до 8 млрд.
...
Рейтинг: 0 / 0
13.06.2011, 16:25
| Ответить | Цитировать | Написать  
Найти позицию кратчайшей последовательность в списке A в котором встречаются все значения
    #37306708
dubov1994
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
dubov1994
Гость
AndreTM,

а чем бинпоиск плох? :)
...
Рейтинг: 0 / 0
13.06.2011, 16:58
| Ответить | Цитировать | Написать  
Найти позицию кратчайшей последовательность в списке A в котором встречаются все значения
    #37306760
Фотография Вот те на
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Вот те на
Участник
dubov1994,

Слушай а как ты определяешь верен
алгоритм или нет. Может научишь? :)
...
Рейтинг: 0 / 0
13.06.2011, 17:39
| Ответить | Цитировать | Написать  
Найти позицию кратчайшей последовательность в списке A в котором встречаются все значения
    #37306768
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Вот те наdubov1994,

Слушай а как ты определяешь верен
алгоритм или нет. Может научишь? :)
Это фундаментальная проблема. Над ней (ИМХО) еще Гёдель ломал моск.
Нет тестов которые-бы показали что алгорим верен в общем случае.
Но есть возможность указать частные случаи, когда алгоритм не работает
(прогнать десяток модульных тестов). Забавно но сколько-бы тестов
не прогоняли всё равно нет доказательства что в алгоритме нет ошибок.
Или правильнее сказать что так тестируют только уж очень простые
алгоритмы. Яркий пример сложных алгоритмов - это современное ПО.
Опрационки, драйверы, прочий софт. В них изначально заложены
ошибки. Часть из них - детектируют. Часть остаётся навсегда
неизвестными.
...
Рейтинг: 0 / 0
13.06.2011, 17:54
| Ответить | Цитировать | Написать  
Найти позицию кратчайшей последовательность в списке A в котором встречаются все значения
    #37306808
Фотография ZyK_BotaN
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ZyK_BotaN
Участник
Вот те наdubov1994,

Слушай а как ты определяешь верен
алгоритм или нет. Может научишь? :)

в принципе можно доказать корректность алгоритма рассматривая инварианты цикла, но мне больше нравится декларативный код, где этих циклов нет.

вот в правильности логики приведенного мной решения я почти уверен, разве что где сделал опечатку. ну и не рассмотрен случай когда такой последовательности нет.
а уверен, потому, что решение простое.
...
Рейтинг: 0 / 0
13.06.2011, 18:29
| Ответить | Цитировать | Написать  
Найти позицию кратчайшей последовательность в списке A в котором встречаются все значения
    #37306814
Фотография Вот те на
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Вот те на
Участник
ZyK_BotaN,

Это эф шарп?
Эх никак не могу я сойти
с иглы си шарпов - ломка. :(
...
Рейтинг: 0 / 0
13.06.2011, 18:35
| Ответить | Цитировать | Написать  
Найти позицию кратчайшей последовательность в списке A в котором встречаются все значения
    #37306818
Фотография ZyK_BotaN
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ZyK_BotaN
Участник
Вот те наZyK_BotaN,

Это эф шарп?
Эх никак не могу я сойти
с иглы си шарпов - ломка. :(
можно подобный код и на С# написать.
для этого нужно заюзать линк.

вот книга хорошая,
учит ФП, не отходя от С-Шарпа, а если быть точнее, там идут примеры паралельно
и на С-Шарпе и на Эф-Шарпе
http://www.manning.com/petricek/
...
Рейтинг: 0 / 0
13.06.2011, 18:40
| Ответить | Цитировать | Написать  
Найти позицию кратчайшей последовательность в списке A в котором встречаются все значения
    #37306820
Фотография ZyK_BotaN
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ZyK_BotaN
Участник
Вот те на,

суть кода прокомментировать нужно? или и так все понятно?
...
Рейтинг: 0 / 0
13.06.2011, 18:41
| Ответить | Цитировать | Написать  
Найти позицию кратчайшей последовательность в списке A в котором встречаются все значения
    #37306822
Фотография Вот те на
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Вот те на
Участник
ZyK_BotaNВот те на,

суть кода прокомментировать нужно? или и так все понятно?

Не надо разберемся.
...
Рейтинг: 0 / 0
13.06.2011, 18:43
| Ответить | Цитировать | Написать  
Найти позицию кратчайшей последовательность в списке A в котором встречаются все значения
    #37306823
Фотография ZyK_BotaN
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ZyK_BotaN
Участник
Вот те наZyK_BotaNВот те на,

суть кода прокомментировать нужно? или и так все понятно?

Не надо разберемся.

мужик ))
...
Рейтинг: 0 / 0
13.06.2011, 18:44
| Ответить | Цитировать | Написать  
Найти позицию кратчайшей последовательность в списке A в котором встречаются все значения
    #37307048
Фотография AndreTM
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AndreTM
Участник
Я всё-таки сделал прогу с учётом всех условий, но стесняюсь выкладывать.
Ибо тестил на VB прямо в офисе (ну нету у меня на офисном компе C-компилятора )
Код, конечно, не оптимизирован вообще. Но это дело недолгое...
...
Рейтинг: 0 / 0
13.06.2011, 23:48
| Ответить | Цитировать | Написать  
Найти позицию кратчайшей последовательность в списке A в котором встречаются все значения
    #37307053
Фотография ZyK_BotaN
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ZyK_BotaN
Участник
AndreTMЯ всё-таки сделал прогу с учётом всех условий, но стесняюсь выкладывать.
Ибо тестил на VB прямо в офисе (ну нету у меня на офисном компе C-компилятора )
Код, конечно, не оптимизирован вообще. Но это дело недолгое...

а что порочного в вб? выкладывай исходники на форум ))
...
Рейтинг: 0 / 0
13.06.2011, 23:51
| Ответить | Цитировать | Написать  
Найти позицию кратчайшей последовательность в списке A в котором встречаются все значения
    #37310640
Фотография AndreTM
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AndreTM
Участник
Вот табличка и исходники на VBA. Варианты с минимизацией затрат по памяти или по кличеству операций в инварианте.
...
Рейтинг: 0 / 0
16.06.2011, 11:51
| Ответить | Цитировать | Написать  
20 сообщений из 45, страница 2 из 2
  2  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Найти позицию кратчайшей последовательность в списке A в котором встречаются все значения
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&msg=37310640&tid=1342882]:
 0ms
get settings:
 7ms
get forum list:
 14ms
check forum access:
 2ms
check topic access:
 2ms
track hit:
 160ms
get topic data:
 9ms
get forum data:
 2ms
get page messages:
 62ms
get tp. blocked users:
 1ms
others: 208ms
total:  467ms
созд. / загр.: 467ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]