Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1]   Вниз
  Печать  
Автор Тема: Взаимно простые числа  (Прочитано 12986 раз)
0 Пользователей и 1 Гость смотрят эту тему.
and
Читатель

by
Offline Offline

« : 19-03-2013 13:26 » new

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


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

Добавлено через 10 минут и 30 секунд:
подскажите как в этом случае работать с графом, много где читал про него понял что у него есть вершины и ребра и все , а как с ним работать не понял. Объясните!
« Последнее редактирование: 19-03-2013 13:36 от and » Записан
RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #1 : 19-03-2013 16:30 » 

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

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
and
Читатель

by
Offline Offline

« Ответ #2 : 19-03-2013 16:39 » 

есть предположения......можно просто пустить два цикла и в них находить НОД a[i]  и a[j],если НОД равен 1 , то счетчик +1.....кстати я школьник.....сегодня была олимпиада....ну т.к. она прошла , поэтому я прорешиваю все что сегодня было
« Последнее редактирование: 19-03-2013 19:10 от Sla » Записан
Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #3 : 19-03-2013 17:50 » 

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

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

P.S. И, кстати, причём тут графы?
« Последнее редактирование: 19-03-2013 17:52 от Dimka » Записан

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
Dmitry
Помогающий

ru
Offline Offline

« Ответ #4 : 19-03-2013 18:46 » 

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

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

ru
Offline Offline
Пол: Мужской

« Ответ #5 : 19-03-2013 18:55 » 

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

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
Dmitry
Помогающий

ru
Offline Offline

« Ответ #6 : 19-03-2013 19:00 » 

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

ru
Offline Offline
Пол: Мужской

« Ответ #7 : 19-03-2013 21:15 » 

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

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
Dmitry
Помогающий

ru
Offline Offline

« Ответ #8 : 20-03-2013 09:43 » 

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

ru
Offline Offline
Пол: Мужской

« Ответ #9 : 20-03-2013 11:06 » 

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

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
Dmitry
Помогающий

ru
Offline Offline

« Ответ #10 : 20-03-2013 11:55 » 

Dimka, в условии же не сказано, что нужно найти самую длинную подпоследовательность. Нужна только её длина. Так что мой вариант не хуже, а даже лучше для данной задачи, т.к. для хранения состояния нужен только массив длиной N (количество чисел в последовательности).
« Последнее редактирование: 20-03-2013 12:00 от Dmitry » Записан
and
Читатель

by
Offline Offline

« Ответ #11 : 20-03-2013 12:29 » 

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

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

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

ru
Offline Offline
Пол: Мужской

« Ответ #12 : 20-03-2013 14:16 » 

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

Цитата: and
я создавал тему когда была олимпиада
Наверно это как-то не совсем честно. Это ж твоя олимпиада, а не наша.

Цитата: and
мне сказали что задача решается с помощью графов
Это верное утверждение, но не единственно верное. Лучше думать своей головой, чем слушать то, что тебе говорят разные доброжелатели.

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

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
Страниц: [1]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines