Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.67/6: Рейтинг темы: голосов - 6, средняя оценка - 4.67
llord
1 / 1 / 0
Регистрация: 14.02.2016
Сообщений: 66
1

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

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

Дано натуральное число n. Укажите все тройки x, y, z таких натуральных чисел, что x2+y2+z2=n.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.02.2016, 19:14
Ответы с готовыми решениями:

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

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

Вывести все комбинации из указанного набора чисел, сумма которых не превышает заданное число
Всем привет. Поставлена такая задача - предположим, что есть массив из трех...

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

Даны натуральное число n. Среди чисел 1, 2, …, n найти все те, которые можно представить в виде суммы квадратов двух натуральных чисел.
Собственно само задание. 5). Даны натуральное число n. Среди чисел 1, 2, …,...

8
Timbl4
19 / 19 / 20
Регистрация: 21.12.2015
Сообщений: 32
19.02.2016, 14:02 2
вроде работает
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
llord
1 / 1 / 0
Регистрация: 14.02.2016
Сообщений: 66
02.04.2016, 21:07  [ТС] 3
Timbl4, где
cin?
0
lemegeton
2935 / 1364 / 467
Регистрация: 29.11.2010
Сообщений: 2,725
03.04.2016, 00:04 4
Цитата Сообщение от llord Посмотреть сообщение
где
cin?
Предполагая, что в предложенном коде вы можете найти его поиском, ответ такой: cin находится в библиотеке iostream, в namespace std.
0
TheCalligrapher
С чаем беда...
Эксперт CЭксперт С++
4834 / 2479 / 695
Регистрация: 18.10.2014
Сообщений: 4,285
03.04.2016, 01:30 5
Цитата Сообщение от 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);
}
Код
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
2935 / 1364 / 467
Регистрация: 29.11.2010
Сообщений: 2,725
03.04.2016, 02:37 6
Крутой подход.
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
В реализации ниже я использовал свою функцию is_square (по ссылке)
Несмотря на целочисленные достоинства, она во много раз(!) медленнее банального сравнения корня и целого от корня. Особенно на больших числах.

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

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

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

Цитата Сообщение от TheCalligrapher Посмотреть сообщение
Достаточно сравнить время генерации разложения для числа 12345 в моем варианте и в варианте с буквальным перебором всех троек из поста номер 2.
Ваш вариант имеет квадратную асимптотическую сложность, предыдущий -- кубическую. Ещё бы он не был быстрее.
0
TheCalligrapher
С чаем беда...
Эксперт CЭксперт С++
4834 / 2479 / 695
Регистрация: 18.10.2014
Сообщений: 4,285
03.04.2016, 03:42 9
Цитата Сообщение от lemegeton Посмотреть сообщение
Сомнительный тезис.
Под "это всем понятно" я имел к виду то, что об этом уже говорилось в прилинкованной теме об определении квадратности числа, из которой я и притащил сюда свою функцию.
0
03.04.2016, 03:42
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.04.2016, 03:42

Даны натуральное число n. Среди чисел 1, 2, …, n найти все те, которые можно представить в виде суммы квадратов двух натуральных чисел
Даны натуральное число n. Среди чисел 1, 2, …, n найти все те, которые можно...

Можно ли заданное натуральное число М представить в виде суммы квадратов двух натуральных чисел?
Можно ли заданное натуральное число М представить в виде суммы квадратов двух...

Ввести натуральное число n. Среди чисел 1,.,n найти все такие числа, запись которых совпадает с последними цифрами
Ввести натуральное число n. Среди чисел 1,...,n найти все такие числа, запись...


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

Или воспользуйтесь поиском по форуму:
9
Ответ Создать тему
Опции темы

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