Количество всех различных представлений числа

@papirus · Регистрация: 21.07.2009

Студворк — интернет-сервис помощи студентам

известно что любое натуральное число N(0<N<=1000) может быть представлено в виде суммы квадратов не более 4-ех положительных целых чисел.Написать программу, которая на ввод числа N, выводит количество S всех различных представлений этого числа. Представления которые отличаются лишь порядком слагаемых, считаются одинаковыми.
например: N=4: S=2 (1^2+1^2+1^2+1^2=4, 2^2=4)

мне не нужно решение, просто не могу сообразить как искать все эти представления?

@Iworb · 15.03.2010, 18:58

Число делишь на 4, извлекаешь корень, вычитаешь из основного числа целую часть полученного. Потом делишь то что получил на 3, извлекаешь корень, вычитаешь из того, что получил в первый раз целую часть второго корня и т.д. Если после 4й итерации остаток от деления 0 - то вот она - успешная комбинация.

Это сырая версия и чисто предположение.

@papirus · 15.03.2010, 19:03 **[ТС]**

Iworb, а если их будет несколько?

@Iworb · 15.03.2010, 19:06

Сообщение от papirus

их

кого?

Добавлено через 43 секунды
если число доходит до нуля на 3ей итерации, то вот - сумма квадратов 3х чисел

Day · 15.03.2010, 19:07

Нужно генерировать НЕУБЫВАЮЩИЕ последовательности из 4 чисел (тогда извегается повторение)
Начальная - 1 1 1 1 (или 0 0 0 0)
Генерация следующего набора:
двигаемся с 1-го элемента пока не произойдет скачок или не упремся в последний
Число перед скачком увеличиваем на 1, все предыдущие сбрасываем в 1
И так пока последнее число не станет >= sqrt(N)
Пример
1 1 1 1
1 1 1 2
1 1 2 2
....
2 2 2 2
1 1 1 3
1 1 2 3
......
Ну и проверяем, не равна ли сумма квадратов N
Пока писал, понял, что можно оптимизировать.
Наборы генерить 1 раз (а не для кажного N) и в массиве отмечать (++) полученные суммы квадратов
ЗЫ. ИМХО, эта тема уместнее в разделе Математика

@Iworb · 15.03.2010, 19:12

попробуем например 151
151/4=37,75
корень = 6,14, т.е. 6 - целая часть
151-36=115
115/3=38
корень = 6
115-36=79
79/2=39,5
корень = 6
79-36=43
43/1=43
корень = 6
значит 151=4*(6^2)+7
невозможно представить - неполучилось....

Добавлено через 50 секунд
да, бредовый у меня вариант вышел наверное...... =(

@papirus · 15.03.2010, 19:25 **[ТС]**

Day, не совсем понятно какими должны быть наборы?

Добавлено через 43 секунды
как они должны генерироваться?

Day · 15.03.2010, 19:27

papirus, алгоритм работает, недавно с его помощью мы решали Обобщенную Большую Теорему Ферма.
Внимательнее вчитался в условие, конечно начинать надо с "0 0 0 0", сбрасывать меньшие индексы тоже в 0 и условие окончания >sqrt(N)

@Eugeniy · 15.03.2010, 19:56

Day, не обобщенную БТФ, а проблему Варинга!
Просто я за реальные названия вещей!
papirus, предложеный тебе метод решения - это фактически грамотный перебор
всех возможных полных квадратов, которые удовлетворяют твоему условию.

Day · 15.03.2010, 20:15

C
1
2
3
4
5
6
static int M[4] = { 0, 0, 0, 0 };
    for(js=0; js<3; js++) if (M[js] < M[js+1]) break;
    M[js] ++;
    for(i=0; i<js; i++) M[i] = 0;
    if (M[3] > sqrt(N)) return(-1);  // Конец перебора
    return(0);

Добавлено через 15 минут
Eugeniy, Проблема Варинга - это тема этого топика. А форомулировка нашей задачи:
Дано N, K
Найдется ли такой набор из N целых, что сумма их K-тых степеней тоже будет K-той степенью.
N=K=2 - Да! Обычные Пифагоровы числа
N > 2 K=2 - БТФ - Нет!
N = K = 3 - Да
N = 4 K = 5 - Как ни странно, Да (133 + 110 + 84 + 27 = 144 - Все числа в 5-степени
N = 5 K = 5 - Да! Найдено нами
N = 6 K = 6 ???
К ПВ это имеет только то отношение, что обе они из аддитивной теории чисел.
ПВ нашим изысканиям не помогает, т.к. базис растет очень быстро с увеличением степени

@papirus · 16.03.2010, 17:29 **[ТС]**

Day, если не затруднит мог бы ты написать код?

Добавлено через 1 минуту
не могу чета в курить

Добавлено через 43 секунды

Сообщение от Day

static int M[4] = { 0, 0, 0, 0 };
for(js=0; js<3; js++) if (M[js] < M[js+1]) break;
M[js] ++;
for(i=0; i<js; i++) M[i] = 0;
if (M[3] > sqrt(N)) return(-1); // Конец перебора
return(0);

как это работает?

Добавлено через 41 секунду
и как быть если будет несколько наборов?

Добавлено через 3 часа 38 минут
пожалуста

Новые блоги и статьи Все статьи Все блоги /
Модель здравосоХранения 6. ESG-повестка и устойчивое развитие; углублённый анализ кадрового бренда anaschu 31.03.2026 В прикрепленном документе раздумья о том, как можно поменять модель в будущем	10 пpимет, которые всегда сбываются Maks 31.03.2026 1. Чтобы, наконец, пришла маршрутка, надо закурить. Если сигарета последняя, маршрутка придет еще до второй затяжки даже вопреки расписанию. 2. Нaдоели зима и снег? Не надо переезжать. Достаточно. . .	Перемещение выделенных строк ТЧ из одного документа в другой Maks 31.03.2026 Реализация из решения ниже выполнена на примере нетипового документа "ВыдачаОборудованияНаСпецтехнику" с единственной табличной частью "ОборудованиеИКомплектующие" разработанного в конфигурации КА2. . . .	Functional First Web Framework Suave DevAlt 30.03.2026 Sauve. IO Апнулись до NET10. Из зависимостей один пакет, работает одинаково хорошо как в режиме проекта так и в интерактивном режиме. из сложностей - чисто функциональный подход. Решил. . .
Автоматическое создание документа при проведении другого документа Maks 29.03.2026 Реализация из решения ниже выполнена на нетиповых документах, разработанных в конфигурации КА2. Есть нетиповой документ "ЗаявкаНаРемонтСпецтехники" и нетиповой документ "ПланированиеСпецтехники". В. . .	Настройка движения справочника по регистру сведений Maks 29.03.2026 Решение ниже реализовано на примере нетипового справочника "ТарифыМобильнойСвязи" разработанного в конфигурации КА2, с целью учета корпоративной мобильной связи в коммерческом предприятии. . . .	Автозаполнение реквизита при выборе элемента справочника Maks 27.03.2026 Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. При выборе "Спецтехники" (Тип Справочник. Спецтехника), заполняется. . .	Сумматор с применением элементов трёх состояний. Hrethgir 26.03.2026 Тут. https:/ / fips. ru/ EGD/ ab3c85c8-836d-4866-871b-c2f0c5d77fbc Первый документ красиво выглядит, но без схемы. Это конечно не даёт никаких плюсов автору, но тем не менее. . . всё может быть. . .

@papirus 2 / 2 / 3 Регистрация: 21.07.2009 Сообщений: 49

	Количество всех различных представлений числа 15.03.2010, 18:48. Показов 2093. Ответов 10 Метки нет (Все метки) известно что любое натуральное число N(0<N<=1000) может быть представлено в виде суммы квадратов не более 4-ех положительных целых чисел.Написать программу, которая на ввод числа N, выводит количество S всех различных представлений этого числа. Представления которые отличаются лишь порядком слагаемых, считаются одинаковыми. например: N=4: S=2 (1^2+1^2+1^2+1^2=4, 2^2=4) мне не нужно решение, просто не могу сообразить как искать все эти представления? 0

@Iworb анимешник++ 95 / 62 / 7 Регистрация: 03.11.2009 Сообщений: 427
	15.03.2010, 18:58
	Число делишь на 4, извлекаешь корень, вычитаешь из основного числа целую часть полученного. Потом делишь то что получил на 3, извлекаешь корень, вычитаешь из того, что получил в первый раз целую часть второго корня и т.д. Если после 4й итерации остаток от деления 0 - то вот она - успешная комбинация. Это сырая версия и чисто предположение. 1

@papirus 2 / 2 / 3 Регистрация: 21.07.2009 Сообщений: 49
	15.03.2010, 19:03 [ТС]
	Iworb, а если их будет несколько? 0

Day 1180 / 990 / 83 Регистрация: 29.10.2009 Сообщений: 1,385
	15.03.2010, 19:07
	Нужно генерировать НЕУБЫВАЮЩИЕ последовательности из 4 чисел (тогда извегается повторение) Начальная - 1 1 1 1 (или 0 0 0 0) Генерация следующего набора: двигаемся с 1-го элемента пока не произойдет скачок или не упремся в последний Число перед скачком увеличиваем на 1, все предыдущие сбрасываем в 1 И так пока последнее число не станет >= sqrt(N) Пример 1 1 1 1 1 1 1 2 1 1 2 2 .... 2 2 2 2 1 1 1 3 1 1 2 3 ...... Ну и проверяем, не равна ли сумма квадратов N Пока писал, понял, что можно оптимизировать. Наборы генерить 1 раз (а не для кажного N) и в массиве отмечать (++) полученные суммы квадратов ЗЫ. ИМХО, эта тема уместнее в разделе Математика 2

@Iworb анимешник++ 95 / 62 / 7 Регистрация: 03.11.2009 Сообщений: 427
	15.03.2010, 19:12
	попробуем например 151 151/4=37,75 корень = 6,14, т.е. 6 - целая часть 151-36=115 115/3=38 корень = 6 115-36=79 79/2=39,5 корень = 6 79-36=43 43/1=43 корень = 6 значит 151=4(6^2)+7 невозможно представить - неполучилось.... Добавлено через 50 секунд* да, бредовый у меня вариант вышел наверное...... =( 1

@papirus 2 / 2 / 3 Регистрация: 21.07.2009 Сообщений: 49
	15.03.2010, 19:25 [ТС]
	Day, не совсем понятно какими должны быть наборы? Добавлено через 43 секунды как они должны генерироваться? 0

Day 1180 / 990 / 83 Регистрация: 29.10.2009 Сообщений: 1,385
	15.03.2010, 19:27
	papirus, алгоритм работает, недавно с его помощью мы решали Обобщенную Большую Теорему Ферма. Внимательнее вчитался в условие, конечно начинать надо с "0 0 0 0", сбрасывать меньшие индексы тоже в 0 и условие окончания >sqrt(N) 1

@Eugeniy 3132 / 1325 / 156 Регистрация: 19.12.2009 Сообщений: 1,808
	15.03.2010, 19:56
	Day, не обобщенную БТФ, а проблему Варинга! Просто я за реальные названия вещей! papirus, предложеный тебе метод решения - это фактически грамотный перебор всех возможных полных квадратов, которые удовлетворяют твоему условию. 0