Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 05.09.2009, 03:59
гость

 
Сообщений: n/a

задача на очередь
Подскажите алгоритм решения такой задачи.
Дано натуральное N и три простых числа P1, P2, P3. Найти N-ое по величине из натуральных чисел, в разложение которых на простые множители входят только числа P1, P2 и P3.
Вход:
В текстовом файле INPUT.TXT записаны числа N (1 <= N <= 10000), P1, P2, P3
( 2 <= P1 < P2 < P3 < 1000000).
Выход:
В текстовый файл OUTPUT.TXT записать найденное число.
Пример входа:
100 3 7 101
Пример выхода:
1697507
  #2  
Старый 01.10.2009, 18:16
Новичок

Отправить личное сообщение для petinv Посмотреть профиль Найти все сообщения от petinv
 
Регистрация: 21.09.2009
Адрес: Петербург
Сообщений: 4

Нужно найти такое X1, что P1^(X1-1) < P2, a P1^(X1) > P2.
После этого последовательно перебираем произведения (P1^K1)*(P2^K2),
где изначально K1 и K2 равны 1, и K1 на каждом шаге увеличивается на 1 пока не достигнет значения X1. После этого K1 приравнивается к 1, а K2 увеличивается на 1.
Продолжаем этот процесс до тех пор, пока не найдем такую пару (K1,K2),
при которой (P1^(K1-1))*(P2^(K2-1)) < P3, а (P1^(K1))*(P2^(K2-1)) > P3 и K1<X1,
либо, (P1^(1))*(P2^(K2)) > P3 и K1=X1.
Обозначим найденные значения K1 и K2 за X21 и X22 соответственно. Теперь можно перебирать произведения
(P1^K1)*(P2^K2)*(P3^K3) с начальными значениями K1=K2=K3=1, увеличивая на каждом шаге K1 на 1 и делая следующие две проверки.
Первая:если K1=X1, то увеличим K2 на 1, а K1 приравняем к 1.
Вторая: если K1=X21 и K2=X22, то увеличим K3 на 1, а K1 и K2 приравняем к 1. (Вторая проверка делается до первой).
Таким образом нужно сделать N шагов.
Алгоритм не самый лучший, но самый простой в описании.

Последний раз редактировалось petinv, 01.10.2009 в 18:39.
  #3  
Старый 01.10.2009, 19:36
Новичок

Отправить личное сообщение для petinv Посмотреть профиль Найти все сообщения от petinv
 
Регистрация: 21.09.2009
Адрес: Петербург
Сообщений: 4

Прошу прощения. Поторопился опубликовать алгоритм. Нужны дополнительные проверки. Когда K2 такое, что P1^(X1+1) < P2^(K2) алгоритм не найдёт некоторые произведения.
  #4  
Старый 07.10.2009, 08:18
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

до кучи - задача рассмотрена в книге Дейкстры "Дисциплина программирования"
  #5  
Старый 10.01.2011, 05:53
гость_102901

 
Сообщений: n/a

Решение
Решение этой задачи описано в книге: А. Шень "Программирование. Теоремы и задачи".
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
очередь с приоритетом гость Реализация, исходники, языки 1 16.11.2008 11:41
Стек и очередь. Не до конца понял смысл. Alexander_ua Задачи 4 06.11.2008 23:49
как реализовать очередь на массиве курсоров? гость Реализация, исходники, языки 0 03.05.2008 18:44