Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Найти ближайшее квадратичное число, и остаток 
:(
    Опции темы
tishaishii
Дата 19.4.2006, 15:51 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Создатель
***


Профиль
Группа: Завсегдатай
Сообщений: 1262
Регистрация: 14.2.2006
Где: Москва

Репутация: нет
Всего: 8
Надо быстро найти ближайшее квадратичное число и остаток.
Например, дано целое неотрицательное число Б=27, надо найти число В=25, число Г=5 и число Е=2
Итого: Б=Г^2+Е=В+Е. 
PM MAIL ICQ Skype   Вверх
nostromo
Дата 19.4.2006, 16:29 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 194
Регистрация: 23.3.2006

Репутация: 5
Всего: 10
Пусть [x] --- целая часть числа x, тогда

Г = [sqrt(Б)],
E = Б - Г^2.
 
--------------------
На пыльных тропинках далеких планет останутся наши следы.
PM MAIL   Вверх
SoWa
Дата 20.4.2006, 11:15 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Харекришна
****


Профиль
Группа: Комодератор
Сообщений: 2422
Регистрация: 18.10.2004

Репутация: 6
Всего: 74
Возможен перебор типа:
Код

for i:=x downto 0 do
begin
if trunc(sqrt(i))=sqrt(i) then 
 Г=sqrt(i)
 E=i 
end;
 


--------------------
Всем добра smile
PM MAIL ICQ   Вверх
nostromo
Дата 20.4.2006, 12:37 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 194
Регистрация: 23.3.2006

Репутация: 5
Всего: 10
Что-то не то вы написали, уважаемый SoWa.
В результате выполнения вашего цикла в перменных Г и Е окажется 0 независимо от x.  smile  
--------------------
На пыльных тропинках далеких планет останутся наши следы.
PM MAIL   Вверх
SoWa
Дата 20.4.2006, 13:53 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Харекришна
****


Профиль
Группа: Комодератор
Сообщений: 2422
Регистрация: 18.10.2004

Репутация: 6
Всего: 74
Ничего подобного, идет проверка, когда корень будет целым числом. Вот и все. Твое решение конечно лучше, но я предложил просто другой способ. 


--------------------
Всем добра smile
PM MAIL ICQ   Вверх
nostromo
Дата 20.4.2006, 14:21 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 194
Регистрация: 23.3.2006

Репутация: 5
Всего: 10
Ну во-первых --- это не откомпилируется (кажется, это Паскаль), а во-вторых, на последней инерации цикла при i=0 условие всегда сработает.
 
--------------------
На пыльных тропинках далеких планет останутся наши следы.
PM MAIL   Вверх
Illuminaty
Дата 20.4.2006, 14:28 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


/*Антон Захаров*/
***


Профиль
Группа: Комодератор
Сообщений: 1238
Регистрация: 19.3.2005
Где: Россия, Казань

Репутация: 1
Всего: 56
nostromo, в твоем алгоритме стоит еще проверить какое число ближе к x: [sqrt(Б)]^2 или ([sqrt(Б)]+1)^2
Если Б=35, то по твоему алгоритму Г=5, хотя ближайшее квадратичное число B=36, а не 25. 
PM MAIL ICQ   Вверх
nostromo
Дата 20.4.2006, 14:38 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 194
Регистрация: 23.3.2006

Репутация: 5
Всего: 10
Согласен.

Г1 := [sqrt(Б)].
Г2 := Г1 +1.

... бла-бла-бла
 
--------------------
На пыльных тропинках далеких планет останутся наши следы.
PM MAIL   Вверх
tishaishii
Дата 24.4.2006, 07:41 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Создатель
***


Профиль
Группа: Завсегдатай
Сообщений: 1262
Регистрация: 14.2.2006
Где: Москва

Репутация: нет
Всего: 8
Ну какой-то способ вы предлагаете совсем не быстрый. Мне он не подойдёт. Нахождение корня, деление и т.д. - это же очень долго.
Может быть, мои рассуждения помогут.

x[i+2]=x[i+1]-x[i]+2

Где x - квадратичное число.
Но я пока задачу не решил. 
PM MAIL ICQ Skype   Вверх
nostromo
Дата 24.4.2006, 09:30 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 194
Регистрация: 23.3.2006

Репутация: 5
Всего: 10
Предлагаю указать диапазон возможных входных значений и платформу (есть ли там математический сопроцессор?). 
Для сравнительно малых входных значений проще и быстрее вычислять корни или хранить таблицу квадратов чисел с последующим поиском по ней.

Добавлено @ 09:39 
Рассуждения не понял:
25 = 16 - 9 + 2 ???
В чем идея?

Может, нужно найти "квадратичные" числа сразу для ряда чисел? 
--------------------
На пыльных тропинках далеких планет останутся наши следы.
PM MAIL   Вверх
MBo
Дата 24.4.2006, 09:50 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 234
Регистрация: 10.6.2002

Репутация: 5
Всего: 18
Код

var
  N, Q, QSqrt, Rem: Integer;
begin
  N := 31;
  Rem := -N;
  QSqrt := -1;
  while Rem < 0 do begin
    Inc(QSqrt, 2);
    Inc(Rem, QSqrt);
  end;
  QSqrt := QSqrt div 2;
  Q := QSqrt * QSqrt;
  if N - Q < Rem then
    Rem := N - Q
  else begin
    Q := N + Rem;
    Inc(QSqrt)
  end;
  Caption := Format('N: %d  корень: %d  квадрат: %d  отклонение: %d',
    [N, QSqrt, Q, Rem]);

 
PM MAIL   Вверх
nostromo
Дата 24.4.2006, 11:19 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 194
Регистрация: 23.3.2006

Репутация: 5
Всего: 10
???

Может, так:
Код

var
  N, Q, QSqrt, q1, q2, Rem: Integer;
begin
  N := 31;
  QSqrt := trunc(sqrt(N));
  q1 := QSqrt * QSqrt;
  q2 := (QSqrt+1) * (QSqrt+1);
  if (N-q1) > (q2-N) then
      QSqrt := QSqrt + 1;
  end;
  Q := QSqrt * QSqrt;
  Rem := abs(N - Q);
  Caption := Format('N: %d  корень: %d  квадрат: %d  отклонение: %d',
    [N, QSqrt, Q, Rem]);
 
--------------------
На пыльных тропинках далеких планет останутся наши следы.
PM MAIL   Вверх
MBo
Дата 24.4.2006, 12:52 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 234
Регистрация: 10.6.2002

Репутация: 5
Всего: 18
nostromo

Я привел метод без использования Sqrt, округления и вообще без вещественной арифметики, раз уж автору это интересно.
Конечно, для больших чисел выгоднее корень извлечь.
 
PM MAIL   Вверх
nostromo
Дата 24.4.2006, 13:21 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 194
Регистрация: 23.3.2006

Репутация: 5
Всего: 10
Виноват. Мне показалось, что это не Вы, а автор темы привел кусок неработающего кода.

У меня нет под руками Паскаля, но, клянусь своей треуголкой, Ваш код, MBo, не может в принципе работать правильно.
Вы его тестировали? Что если поставить N=100?
 
--------------------
На пыльных тропинках далеких планет останутся наши следы.
PM MAIL   Вверх
maxim1000
Дата 24.4.2006, 13:44 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Участник
Сообщений: 3334
Регистрация: 11.1.2003
Где: Киев

Репутация: 33
Всего: 110
для целых чисел можно попробовать метод бисекции - для 32-битного числа достаточно будет сделать шагов 17, да и операции там простые... 


--------------------
qqq
PM WWW   Вверх
Ответ в темуСоздание новой темы Создание опроса
Правила форума "Алгоритмы"

maxim1000

Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.

Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000.
 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Алгоритмы | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.0993 ]   [ Использовано запросов: 21 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.