|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
10.03.2008, 18:51 | #1 |
Форумчанин
Регистрация: 16.01.2008
Сообщений: 288
|
Задач о квадратных корнях
Задача: разбить введенное число на сумму таких чисел, из которых вычесляется квадратный корень, причем количество чисел дожно быть наименьшим. Например, 5=4+1 6=4+1+1 8=4+4 9=9 12=4+4+4 72=36+36 109=100+9 У кого какие предложения?
|
10.03.2008, 19:18 | #2 |
Участник клуба
Регистрация: 12.10.2007
Сообщений: 1,204
|
1.Берем максимальное целое, квадрат которого не превышает числа - int(sqrt(N))
2.От числа отнимаем квадрат выбранного 3.Если остаток > 0, goto 1 Последний раз редактировалось alexBlack; 10.03.2008 в 19:33. |
10.03.2008, 19:23 | #3 |
Форумчанин
Регистрация: 16.01.2008
Сообщений: 288
|
Да, я то же так думал. Но получается, что 12=9+1+1+1 (что составляет 4 цифры), а нужно что-бы было 12=4+4+4(3 цифры).
|
10.03.2008, 19:28 | #4 |
Участник клуба
Регистрация: 12.10.2007
Сообщений: 1,204
|
А, да, подумаю еще
.... Вот этот код дает возможные разложения кроме самых длинных. Общая идея: полный перебор всех возможных разложений. Но полный перебор был-бы слишком длинным. Поэтому введено ограничение. Алгоритм, который был предложен ранее дает первое приближение. Остальные варианты разложения прерываются как только количество элементов превысит полученное ранее минимальное разложение (lastCount). Код:
9998== 99+14+1 86+51+1 51+86+1 14+99+1 Последний раз редактировалось alexBlack; 10.03.2008 в 20:27. |
10.03.2008, 20:29 | #5 |
Новичок
Джуниор
Регистрация: 18.01.2008
Сообщений: 1,720
|
А вот так:
Берём целое из корня (N/2), возводим в квадрат, отнимаем этот квадрат от N столько раз, сколько получится, над остатком повторяем то же самое... |
10.03.2008, 21:15 | #6 |
Участник клуба
Регистрация: 12.10.2007
Сообщений: 1,204
|
Для 12 нормально, но
100 = 49+49+1+1 Может какая-то теоремка есть по этому поводу ? |
10.03.2008, 21:47 | #7 |
Новичок
Джуниор
Регистрация: 18.01.2008
Сообщений: 1,720
|
|
11.03.2008, 10:04 | #8 | |
Участник клуба
Регистрация: 12.10.2007
Сообщений: 1,204
|
Нашел только вот это:
Цитата:
Код:
Код:
|
|
11.03.2008, 10:31 | #9 |
Новичок
Джуниор
Регистрация: 18.01.2008
Сообщений: 1,720
|
Это всё не совсем то, это неразрешимая (пока?) теорема Ферма. Есть теорема Лагранжа - всякое натуральное число можно представить в виде суммы четырех квадратов. Есть признак Дирихле-Гаусса - число вида (4^k)*(8n + 7), k и n - неотрицательные целые, представить суммой трёх квадратов нельзя. Есть еще признак Жирара: Натуральное число представимо в виде суммы квадратов двух целых чисел тогда и только тогда, когда в его разложение на простые множители любой простой множитель вида (4k + 3) входит в четной степени, и такой слабый: Числа, кратные 3, но не кратные 9, представить в виде суммы двух квадратов нельзя. Но это всё если и можно использовать, то разве что для оптимизации. Есть еще способ подсчёта разложений от Дирихле, но кажется дело всё-таки идет к перебору...
|
11.03.2008, 12:18 | #10 | |
Забанен
Форумчанин Подтвердите свой е-майл
Регистрация: 01.11.2006
Сообщений: 420
|
вот ссылка на подобную задачу
http://acm.timus.ru/problem.aspx?space=1&num=1073 Цитата:
Код:
Если ничто другое не помогает, прочтите, наконец, инструкцию! Аксиома Кана
|
|
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Qu 1.0 - программа для решения квадратных уравнений | DM_bite | Софт | 5 | 20.03.2010 22:37 |
Сравнение 2-ух квадратных матриц размер 3*3 | Artem1987 | Помощь студентам | 2 | 23.03.2008 16:16 |
Три квадратных уравнения. Найти минимальное значение среди действительных корней этих уравнений. Паскаль. | GE076 | Помощь студентам | 2 | 17.12.2007 20:41 |
5 задач | Wander | Помощь студентам | 17 | 01.06.2007 09:17 |