Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
papirus
2 / 2 / 0
Регистрация: 21.07.2009
Сообщений: 49
#1

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

15.03.2010, 18:48. Просмотров 815. Ответов 10
Метки нет (Все метки)

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

мне не нужно решение, просто не могу сообразить как искать все эти представления?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.03.2010, 18:48
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Количество всех различных представлений числа (C++):

Найдите количество всех различных наборов из четырех четных чисел - C++
&quot;Найдите количество всех различных наборов из четырех четных чисел (int a,b,c,d), для которых будет выполнен вызов функции call в данном...

Где хранить глобальную переменную для всех представлений? - C++
я делаю MDI приложение с использованием БД мне нужно чтобы при запуске открывалась БД (CDatabase) а потом все формы использовали бы...

Подсчитать количество различных разбиений числа N на натуральные слагаемые - C++
Условие: требуется подсчитать количество различных разбиений числа N на натуральные слагаемые. Два разложения считаются различными, если...

Найти количество различных цифр данного натурального числа - C++
help #include &quot;stdafx.h&quot; #include &lt;iostream&gt; #include &lt;conio.h&gt; using namespace std; int _tmain(int argc, _TCHAR* argv) { ...

Подсчитать количество различных цифр в десятичной записи натурального числа. - C++
Подсчитать количество различных цифр в десятичной записи натурального числа.

Подсчитать количество различных цифр в десятичной записи натурального числа - C++
Тема: Строки.Множества. 3.1. Напишите программу, которая вводит строку и выводит ее, сокращая каждый раз на 1 символ до тех пор, пока в...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Iworb
анимешник++
93 / 60 / 2
Регистрация: 03.11.2009
Сообщений: 413
15.03.2010, 18:58 #2
Число делишь на 4, извлекаешь корень, вычитаешь из основного числа целую часть полученного. Потом делишь то что получил на 3, извлекаешь корень, вычитаешь из того, что получил в первый раз целую часть второго корня и т.д. Если после 4й итерации остаток от деления 0 - то вот она - успешная комбинация.

Это сырая версия и чисто предположение.
papirus
2 / 2 / 0
Регистрация: 21.07.2009
Сообщений: 49
15.03.2010, 19:03  [ТС] #3
Iworb, а если их будет несколько?
Iworb
анимешник++
93 / 60 / 2
Регистрация: 03.11.2009
Сообщений: 413
15.03.2010, 19:06 #4
Цитата Сообщение от papirus Посмотреть сообщение
их
кого?

Добавлено через 43 секунды
если число доходит до нуля на 3ей итерации, то вот - сумма квадратов 3х чисел
Day
1155 / 960 / 57
Регистрация: 29.10.2009
Сообщений: 1,385
15.03.2010, 19:07 #5
Нужно генерировать НЕУБЫВАЮЩИЕ последовательности из 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
анимешник++
93 / 60 / 2
Регистрация: 03.11.2009
Сообщений: 413
15.03.2010, 19:12 #6
попробуем например 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
2 / 2 / 0
Регистрация: 21.07.2009
Сообщений: 49
15.03.2010, 19:25  [ТС] #7
Day, не совсем понятно какими должны быть наборы?

Добавлено через 43 секунды
как они должны генерироваться?
Day
1155 / 960 / 57
Регистрация: 29.10.2009
Сообщений: 1,385
15.03.2010, 19:27 #8
papirus, алгоритм работает, недавно с его помощью мы решали Обобщенную Большую Теорему Ферма.
Внимательнее вчитался в условие, конечно начинать надо с "0 0 0 0", сбрасывать меньшие индексы тоже в 0 и условие окончания >sqrt(N)
Eugeniy
3119 / 1312 / 141
Регистрация: 19.12.2009
Сообщений: 1,808
15.03.2010, 19:56 #9
Day, не обобщенную БТФ, а проблему Варинга!
Просто я за реальные названия вещей!
papirus, предложеный тебе метод решения - это фактически грамотный перебор
всех возможных полных квадратов, которые удовлетворяют твоему условию.
Day
1155 / 960 / 57
Регистрация: 29.10.2009
Сообщений: 1,385
15.03.2010, 20:15 #10
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
2 / 2 / 0
Регистрация: 21.07.2009
Сообщений: 49
16.03.2010, 17:29  [ТС] #11
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 минут
пожалуста
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.03.2010, 17:29
Привет! Вот еще темы с ответами:

Подсчитать количество различных значащих цифр в десятичной записи натурального числа - C++
Составить программу подсчета количества различных значащих цифр в десятичной записи натурального числа.

Найти количество различных чисел, которые можно получить из числа ровно за C команд - C++
#include &lt;iostream&gt; using namespace std; int c(int x, int y) { if (x == y || y == 0) return 1; else if (y &gt; x) return 0; ...

Дан список, содержащий целые числа. определить количество различных элементов этого списка - C++
...

Подсчет всех различных сумм - C++
Здравствуйте. Мне необходимо реализовать следующее. Есть n наборов чисел по li штук.i=1,n. необходимо посчитать все возможные суммы из...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
16.03.2010, 17:29
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru