1 / 1 / 0
Регистрация: 14.02.2016
Сообщений: 66

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

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

Author24 — интернет-сервис помощи студентам
Дано натуральное число 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
4898 / 2692 / 919
Регистрация: 29.11.2010
Сообщений: 5,780
03.04.2016, 00:04
Цитата Сообщение от llord Посмотреть сообщение
где
cin?
Предполагая, что в предложенном коде вы можете найти его поиском, ответ такой: cin находится в библиотеке iostream, в namespace std.
0
Вездепух
Эксперт CЭксперт С++
 Аватар для TheCalligrapher
12890 / 6752 / 1812
Регистрация: 18.10.2014
Сообщений: 17,080
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
4898 / 2692 / 919
Регистрация: 29.11.2010
Сообщений: 5,780
03.04.2016, 02:37
Крутой подход.
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
В реализации ниже я использовал свою функцию is_square (по ссылке)
Несмотря на целочисленные достоинства, она во много раз(!) медленнее банального сравнения корня и целого от корня. Особенно на больших числах.

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

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

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

Цитата Сообщение от TheCalligrapher Посмотреть сообщение
Достаточно сравнить время генерации разложения для числа 12345 в моем варианте и в варианте с буквальным перебором всех троек из поста номер 2.
Ваш вариант имеет квадратную асимптотическую сложность, предыдущий -- кубическую. Ещё бы он не был быстрее.
0
Вездепух
Эксперт CЭксперт С++
 Аватар для TheCalligrapher
12890 / 6752 / 1812
Регистрация: 18.10.2014
Сообщений: 17,080
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
Ответ Создать тему
Опции темы

Новые блоги и статьи
Анализ и линтинг кода JavaScript: ESLint, Prettier и JSHint
run.dev 26.04.2025
JavaScript прошёл долгий путь от простого языка для анимации веб-страниц до основы современной веб-разработки. С ростом сложности приложений, увеличением кодовых баз и масштабированием команд. . .
Паттерны в Python: Singleton, Factory и Observer
py-thonny 26.04.2025
Паттерны проектирования — это проверенные временем решения типовых проблем разработки программного обеспечения. Их история берёт начало с книги "Приёмы объектно-ориентированного проектирования. . . .
Исключения в C#: Stack Overflow, Access Violation и Out of memory
stackOverflow 26.04.2025
Исключения в C# — это не только механизм оповещения о проблемах, а целое искусство управления потоком выполнения программы в экстремальных ситуациях. Обычное исключение, например,. . .
Логирование в C# ASP.NET Core с помощью Serilog, ElasticSearch, Kibana
stackOverflow 25.04.2025
Помните те времена, когда для анализа проблемы приходилось подключаться к серверу, искать нужный лог-файл среди десятков других и вручную фильтровать тысячи строк в поисках ошибки? К счастью, эти дни. . .
Структура "железный OnKeyUp" вместо антидребезга. Полностью асинхронный счётчик.
Hrethgir 25.04.2025
Программа для симуляции схемы - Logisim Evolution В общем какое-то время отвлёкся, так было надо, теперь когда запилю это на verilog и FPGA , досоставлю заявку в ФИПС на полезную модель - не готов. . .
Автоматизация Amazon Web Services (AWS) с Boto3 в Python
py-thonny 25.04.2025
Облачные вычисления стали неотъемлемой частью современной ИТ-инфраструктуры, а Amazon Web Services (AWS) занимает лидирующие позиции среди провайдеров облачных услуг. Управление многочисленными. . .
Apache Kafka vs RabbitMQ в микросервисной архитектуре
ArchitectMsa 25.04.2025
Современная разработка ПО всё чаще склоняется к микросервисной архитектуре — подходу, при котором приложение разбивается на множество небольших, автономных сервисов. В этой распределённой среде. . .
Параллельное программирование с OpenMP в C++
NullReferenced 24.04.2025
Параллельное программирование — подход к созданию программ, когда одна задача разбивается на несколько подзадач, которые могут выполняться одновременно. Оно стало необходимым навыком для. . .
Цепочки методов в C# с Fluent API
UnmanagedCoder 24.04.2025
Современное программирование — это не только решение функциональных задач, но и создание кода, который удобно поддерживать, расширять и читать. Цепочки методов и Fluent-синтаксис в C# стали мощным. . .
Мульти-тенантные БД с PostgreSQL Row Security
Codd 23.04.2025
Современные облачные сервисы и бизнес-приложения всё чаще обслуживают множество клиентов в рамках единой программной инфраструктуры. Эта архитектурная модель, известная как мульти-тенантность, стала. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru