Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.64/55: Рейтинг темы: голосов - 55, средняя оценка - 4.64
1 / 1 / 0
Регистрация: 14.02.2016
Сообщений: 66

Найти все тройки чисел, сумма квадратов которых даёт заданное натуральное число

18.02.2016, 19:14. Показов 11779. Ответов 8
Метки c++ (Все метки)

Студворк — интернет-сервис помощи студентам
Дано натуральное число n. Укажите все тройки x, y, z таких натуральных чисел, что x2+y2+z2=n.
0
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
18.02.2016, 19:14
Ответы с готовыми решениями:

Найти все тройки чисел, сумма квадратов которых даёт заданное натуральное число
Найти все тройки чисел, сумма квадратов которых даёт заданное натуральное число n=x^2+y^2+z^2 int n; float x, y, z; ...

Натуральное число n вывести все тройки чисел, сумма квадратов, которых равно число n
натуральное число n вывести все тройки чисел,сумма квадратов,которых равно число n

Найти 3 натуральных числа сумма квадратов которых дает заданное число
Перевести с С++ на Си Не знаю как #include <iostream> #include < math.h > using namespace std; int main() { ...

8
20 / 20 / 20
Регистрация: 21.12.2015
Сообщений: 32
19.02.2016, 14:02
вроде работает
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include < math.h > 
 
using namespace std;
 
int main()
{
    setlocale(LC_ALL,"Russian");
    cout<<"Введите n: "<<endl;
    int n;
    cin>>n;
    if(n>0){
    for(float i=1; i<n; i++)
    {
        for(float j=1; j<n; j++)
        {
            for(float q=1; q<n; q++)
            {
                if( pow(i,2)+ pow(j,2)+ pow(q,2)==n)
                    cout<<"i="<< i <<" j="<< j << " q="<< q <<endl;
            }
        }
    }
    }
    else cout<<"n меньше нуля"<<endl;
    system("pause");
}
1
1 / 1 / 0
Регистрация: 14.02.2016
Сообщений: 66
02.04.2016, 21:07  [ТС]
Timbl4, где
cin?
0
 Аватар для lemegeton
4903 / 2696 / 921
Регистрация: 29.11.2010
Сообщений: 5,783
03.04.2016, 00:04
Цитата Сообщение от llord Посмотреть сообщение
где
cin?
Предполагая, что в предложенном коде вы можете найти его поиском, ответ такой: cin находится в библиотеке iostream, в namespace std.
0
Вездепух
Эксперт CЭксперт С++
 Аватар для TheCalligrapher
12938 / 6805 / 1821
Регистрация: 18.10.2014
Сообщений: 17,224
03.04.2016, 01:30
Цитата Сообщение от llord Посмотреть сообщение
Дано натуральное число n. Укажите все тройки x, y, z таких натуральных чисел, что x2+y2+z2=n.
Для избежания повторений (кстати, по условию, надо ли их избегать?) будем рассматривать только тройки вида x <= y <= z. Из этого следует, что x2 должно принадлежать диапазону [1, n/3]. А y2 должно принадлежать диапазону [x, (n - x2)/2].

Будем итерировать только по x и y, и для каждой пары x и y будем вычиcлять z2 = n - x2 - y2. После чего мы будем проверять это значение на квадратичность любым из описанных здесь - Функция проверки числа на полный квадрат - способов. Если z2 является квадратом натурального числа, то мы нашли нашу тройку.

В реализации ниже я использовал свою функцию is_square (по ссылке)

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <cassert>
#include <cmath>
#include <iostream>
 
bool is_square(unsigned n)
{
  if (n <= 1)
    return true;
 
  while (n % 2 == 0)
  {
    n /= 2;
    if (n % 2 != 0)
      return false;
    n /= 2;
  }
 
  unsigned d = 3;
 
  while (d < n)
    if (n % d == 0)
    {
      n /= d;
      if (n % d != 0)
        return false;
      n /= d;
    }
    else
      d += 2;
 
  return n == 1;
}
 
int main()
{
  unsigned n = 12345;
 
  unsigned range_x2 = n / 3;
 
  unsigned x = 1;
  do
  {
    unsigned x2 = x * x;
    if (x2 > range_x2)
      break;
 
    unsigned range_y2 = (n - x2) / 2;
 
    unsigned y = x;
    do
    {
      unsigned y2 = y * y;
      if (y2 > range_y2)
        break;
 
      assert(x2 + y2 < n);
      unsigned z2 = n - x2 - y2;
 
      if (is_square(z2))
        std::cout << x << " " << y << " " << (unsigned) (std::sqrt(z2) + .5) << std::endl;
 
      ++y;
    } while (true);
 
    ++x;
  } while (true);
}
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
4 77 80
7 14 110
7 70 86
8 20 109
13 76 80
20 59 92
22 25 106
22 55 94
25 46 98
32 64 85
43 64 80
46 70 73
53 56 80
55 62 74
1
 Аватар для lemegeton
4903 / 2696 / 921
Регистрация: 29.11.2010
Сообщений: 5,783
03.04.2016, 02:37
Крутой подход.
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
В реализации ниже я использовал свою функцию is_square (по ссылке)
Несмотря на целочисленные достоинства, она во много раз(!) медленнее банального сравнения корня и целого от корня. Особенно на больших числах.

Если задача должна быть выполнена за определённое время, воспользуйтесь сравнением корня и целочисленного значения корня.
0
Вездепух
Эксперт CЭксперт С++
 Аватар для TheCalligrapher
12938 / 6805 / 1821
Регистрация: 18.10.2014
Сообщений: 17,224
03.04.2016, 03:36
Цитата Сообщение от lemegeton Посмотреть сообщение
Несмотря на целочисленные достоинства, она во много раз(!) медленнее банального сравнения корня и целого от корня. Особенно на больших числах.
О, это, всем понятно. В данном случае, как раз таки, использование "медленной" функции прекрасно иллюстрирует тот факт, что если некоторый участок кода является сравнительно некритическим, то и оптимизация (или деоптимизауия) этого участка мало сказывается на общей производительности программы, по крайней мере пока речь идет о порядковых сравнениях. Достаточно сравнить время генерации разложения для числа 12345 в моем варианте и в варианте с буквальным перебором всех троек из поста номер 2.

А также она несет в массы такие неоспоримые человеческие ценности, как великие идеи навязчивой факторизации числа на простые множители и безудержного переиспользования старого кода (и то и другое - к месту и не к месту).

P.S. Если бы мы гонялись за скоростью, то интересно было бы попробовать вот это: http://stackoverflow.com/a/424936/187690 Но это тема совсем для другого разговора.
0
 Аватар для lemegeton
4903 / 2696 / 921
Регистрация: 29.11.2010
Сообщений: 5,783
03.04.2016, 03:38
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
О, это, всем понятно.
Сомнительный тезис.

Цитата Сообщение от TheCalligrapher Посмотреть сообщение
Достаточно сравнить время генерации разложения для числа 12345 в моем варианте и в варианте с буквальным перебором всех троек из поста номер 2.
Ваш вариант имеет квадратную асимптотическую сложность, предыдущий -- кубическую. Ещё бы он не был быстрее.
0
Вездепух
Эксперт CЭксперт С++
 Аватар для TheCalligrapher
12938 / 6805 / 1821
Регистрация: 18.10.2014
Сообщений: 17,224
03.04.2016, 03:42
Цитата Сообщение от lemegeton Посмотреть сообщение
Сомнительный тезис.
Под "это всем понятно" я имел к виду то, что об этом уже говорилось в прилинкованной теме об определении квадратности числа, из которой я и притащил сюда свою функцию.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
03.04.2016, 03:42
Помогаю со студенческими работами здесь

Есть такая задача, Найти все тройки чисел в диапазоне от 1 до 100, для которых сумма квадратов первого и второго чисел равны квадрату третьего числа
Есть задача, Найти все тройки чисел в диапазоне от 1 до 100, для которых сумма квадратов первого и второго чисел равны квадрату третьего...

Найти на отрезке все числа, сумма цифр которых дает заданное
Пользователь вводит числа х, a, b. Из промежутка от a до b найти все числа, сумма цифр которых дает х.

Найти минимальное количество полных квадратов, сумма которых составляет заданное число
Добрый вечер. Как по вашему можно решить эту задачу? SumOfSquares(4) = 1??

Дано двузначное натуральное число m. Получить все двузначные натуральные числа, сумма квадратов цифр которых р
Дано двузначное натуральное число m. Получить все двузначные натуральные числа, сумма квадратов цифр которых равна m (например, если m=13,...

Дано натуральное число n. Найти все Пифагоровые тройки натуральных чисел
Дано натуральное число n. Найти все Пифагоровые тройки натуральных чисел, каждые из которых не превышает n, то есть все такие тройки...


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

Или воспользуйтесь поиском по форуму:
9
Ответ Создать тему
Новые блоги и статьи
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами
8Observer8 20.02.2026
Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .
Конвертировать закладки radiotray-ng в m3u-плейлист
damix 19.02.2026
Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .
Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI
Eddy_Em 18.02.2026
Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .
Камера Toupcam IUA500KMA
Eddy_Em 12.02.2026
Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу
zbw 12.02.2026
И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.
«Знание-Сила»
zbw 12.02.2026
«Знание-Сила» «Время-Деньги» «Деньги -Пуля»
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров
8Observer8 12.02.2026
Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image)
8Observer8 11.02.2026
Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru