Взаимно простые числа

[and]

Здравствуйте!!!!!срочно нужна ваша помощь!нужно написать программу:


Взаимно простые соседи
Дана последовательность из N чисел. Нужно определить длину максимальной подпоследовательности(необязательно подряд идущие) в которой два любых соседних числа взаимно простые.
   Формат ввода:
  N- количество чисел(2<=N<=1000
   далее следует последовательность из N чисел(a)
   Формат вывода:
    Ans- ответ на задачу
   пример ввода
   5
   2  4  7 14 9
   пример вывода
   3
напишите пожалуйста код в Pascal!!!!сам не могу, не знаю графов , а перебором - тысячу делать 
заранее спасибо!!

Добавлено через 10 минут и 30 секунд:
подскажите как в этом случае работать с графом, много где читал про него понял что у него есть вершины и ребра и все , а как с ним работать не понял. Объясните!

[RXL]

Правила читал? Завтра зачет, а к изучению материала приступил только что? Это твоя проблема и тебе ее решать. Максимум можем помочь разобраться. Начинай, а мы подскажем, что верно, что нет и куда двигаться.

[and]

есть предположения......можно просто пустить два цикла и в них находить НОД a[i]  и a[j],если НОД равен 1 , то счетчик +1.....кстати я школьник.....сегодня была олимпиада....ну т.к. она прошла , поэтому я прорешиваю все что сегодня было

[Dimka]

and, если всё закончилось, почему "срочно"?

Давай ты для начала напишешь на Pascal функцию вычисления НОД. Просто, чтобы видеть, какой у тебя уровень.

P.S. И, кстати, причём тут графы?

[Dmitry]

Я правильно понял, для того примера это последовательности 2, 7, 9 и 4, 7, 9?
Ну, если "в лоб", то обход для построение матрицы смежности - O(N!). И поиск максимального пути в ор. графе без циклов.

На олимпиады вроде не заставляют ходить. Если это для себя - то к чему такая помощь?

[Dimka]

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

[Dmitry]

Dimka, я подозревал, что есть решение более красивое, а моё  - ни разу не олимпиадное
Завтра подумаю.

[Dimka]

Dmitry, когда будешь думать, не забывай, что это задача для школьников

[Dmitry]

Dimka, на выспавшуюся голову всё действительно гораздо проще.

(click to show)

При обходе для текущего числа записываем в массив максимальную длину последовательности из уже пройденных элементов, заканчивающуюся этим числом. Т.е. М(i] = M[j] + 1, где i-ое и j-ое числа вз. простые и при этом M[j] максимально. Получается в худшем случае (N-1)! операций НОД, в лучшем - N-1

[Dimka]

Dmitry, я бы хранил все текущие подпоследовательности, добавляя текущее число в те из них, где наблюдается НОД=1 текущего числа с последними членами. Попутно отслеживать, какая из подпоследовательностей самая длинная. В конце остаётся вывести найденную самую длинную подпоследовательность. Если хранить только длины и индексы одного из членов каждой подпоследовательности, в конце восстановление этой подпоследовательности будет фактически аналогичной по сложности задачей, т.к. подпоследовательности могут многократно пересекаться, и на каждой развилке будет непонятно, куда идти дальше - по-моему, менее выгодный по скорости вариант. Учитывая, что олимпиадные задачи оцениваются по скорости работы при лимите памяти 64 Мб, здесь выгоднее тратить память на хранение всех подпоследовательностей.

[Dmitry]

Dimka, в условии же не сказано, что нужно найти самую длинную подпоследовательность. Нужна только её длина. Так что мой вариант не хуже, а даже лучше для данной задачи, т.к. для хранения состояния нужен только массив длиной N (количество чисел в последовательности).

[and]

and, если всё закончилось, почему "срочно"?

Давай ты для начала напишешь на Pascal функцию вычисления НОД. Просто, чтобы видеть, какой у тебя уровень.

P.S. И, кстати, причём тут графы?

1  если всё закончилось, почему "срочно"?я создавал тему когда была олимпиада, мне не ответили. тема осталась....вот я хочу разобраться с этой задачей.
2 И, кстати, причём тут графы?мне сказали что задача решается с помощью графов

[Dimka]

Dmitry, а, да, нужна лишь длина. Тогда не надо хранить подпоследовательности, а достаточно для каждой хранить длину и последний член.

я создавал тему когда была олимпиада

Наверно это как-то не совсем честно. Это ж твоя олимпиада, а не наша.

мне сказали что задача решается с помощью графов

Это верное утверждение, но не единственно верное. Лучше думать своей головой, чем слушать то, что тебе говорят разные доброжелатели.

and, так как там у тебя с функцией вычисления НОД?