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

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

Войти
Регистрация
Восстановить пароль
 
w0nder
0 / 0 / 0
Регистрация: 23.11.2012
Сообщений: 131
#1

Спасайте х( Простое задание на функции, сумма квадратов чисел - C++

28.11.2012, 17:41. Просмотров 679. Ответов 6
Метки нет (Все метки)

Дан интервал натуральных чисел [m,n]. Напечатать на экране все те числа, которые принадлежат этому интервалу и которые можно выразить как сумму квадратов двух натуральных чисел (используя функцию, которая знает квадраты целых чисел)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.11.2012, 17:41     Спасайте х( Простое задание на функции, сумма квадратов чисел
Посмотрите здесь:
C++ Задание на функции - сумма квадратов чисел
Сумма квадратов 3-х чисел C++
сумма квадратов трех чисел C++
Сумма делителей квадратов удвоенных чисел C++
Сумма двух квадратов натуральных чисел C++
Среди двузначных чисел найти те, сумма квадратов цифр которых делится на 13 C++
C++ Среди двузначных чисел найти те, сумма квадратов цифр которых делится на 13
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Kuzia domovenok
1889 / 1744 / 117
Регистрация: 25.03.2012
Сообщений: 5,922
Записей в блоге: 1
28.11.2012, 18:06     Спасайте х( Простое задание на функции, сумма квадратов чисел #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
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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <iostream>
#include <stdint.h>
const uint16_t squares[] = {
    0, 1, 4, 9,
    16, 25, 36, 49,
    64, 81, 100, 121,
    144, 169, 196, 225,
    256, 289, 324, 361,
    400, 441, 484, 529,
    576, 625, 676, 729,
    784, 841, 900, 961,
    1024, 1089, 1156, 1225,
    1296, 1369, 1444, 1521,
    1600, 1681, 1764, 1849,
    1936, 2025, 2116, 2209,
    2304, 2401, 2500, 2601,
    2704, 2809, 2916, 3025,
    3136, 3249, 3364, 3481,
    3600, 3721, 3844, 3969,
    4096, 4225, 4356, 4489,
    4624, 4761, 4900, 5041,
    5184, 5329, 5476, 5625,
    5776, 5929, 6084, 6241,
    6400, 6561, 6724, 6889,
    7056, 7225, 7396, 7569,
    7744, 7921, 8100, 8281,
    8464, 8649, 8836, 9025,
    9216, 9409, 9604, 9801,
    10000, 10201, 10404, 10609,
    10816, 11025, 11236, 11449,
    11664, 11881, 12100, 12321,
    12544, 12769, 12996, 13225,
    13456, 13689, 13924, 14161,
    14400, 14641, 14884, 15129,
    15376, 15625, 15876, 16129,
    16384, 16641, 16900, 17161,
    17424, 17689, 17956, 18225,
    18496, 18769, 19044, 19321,
    19600, 19881, 20164, 20449,
    20736, 21025, 21316, 21609,
    21904, 22201, 22500, 22801,
    23104, 23409, 23716, 24025,
    24336, 24649, 24964, 25281,
    25600, 25921, 26244, 26569,
    26896, 27225, 27556, 27889,
    28224, 28561, 28900, 29241,
    29584, 29929, 30276, 30625,
    30976, 31329, 31684, 32041,
    32400, 32761, 33124, 33489,
    33856, 34225, 34596, 34969,
    35344, 35721, 36100, 36481,
    36864, 37249, 37636, 38025,
    38416, 38809, 39204, 39601,
    40000, 40401, 40804, 41209,
    41616, 42025, 42436, 42849,
    43264, 43681, 44100, 44521,
    44944, 45369, 45796, 46225,
    46656, 47089, 47524, 47961,
    48400, 48841, 49284, 49729,
    50176, 50625, 51076, 51529,
    51984, 52441, 52900, 53361,
    53824, 54289, 54756, 55225,
    55696, 56169, 56644, 57121,
    57600, 58081, 58564, 59049,
    59536, 60025, 60516, 61009,
    61504, 62001, 62500, 63001,
    63504, 64009, 64516, 65025
};
inline int isqrt(uint16_t x) {
    const uint16_t *p = squares;
 
    if (p[128] <= x) p += 128;
    if (p[ 64] <= x) p +=  64;
    if (p[ 32] <= x) p +=  32;
    if (p[ 16] <= x) p +=  16;
    if (p[  8] <= x) p +=   8;
    if (p[  4] <= x) p +=   4;
    if (p[  2] <= x) p +=   2;
    if (p[  1] <= x) p +=   1;
 
    return p - squares;
}
bool is_sum_of_squares(int arg){
     int sqrta=isqrt(arg);
     int sqrtb;
     for (int i=1; i<=sqrta; i++){
         sqrtb=isqrt(arg-i*i);
         if (sqrtb*sqrtb==arg-i*i) return true;
        }
        return false;    
}
int main()
{
    int m, n;
    std::cout<<"Input m n: ";
    std::cin>>m>>n;
    if (m>n) std::swap(m,n);
    for (int i=m; i<=n; i++ )
     if (is_sum_of_squares(i)) std::cout<<i<<", ";
    system("pause");
    return 0;
}
w0nder
0 / 0 / 0
Регистрация: 23.11.2012
Сообщений: 131
28.11.2012, 18:49  [ТС]     Спасайте х( Простое задание на функции, сумма квадратов чисел #3
Спасибо большое, а можно немного добавить комментарии? Я в этом 0
Kuzia domovenok
1889 / 1744 / 117
Регистрация: 25.03.2012
Сообщений: 5,922
Записей в блоге: 1
28.11.2012, 19:09     Спасайте х( Простое задание на функции, сумма квадратов чисел #4
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bool is_sum_of_squares(int arg){    //проверка, является ли arg (например arg=25) суммой квадратов
  int sqrta=isqrt(arg);  //   sqrta=корень из 25=5 
                                 // значит 5*5 - максимальное слагаемое, из которого извлекается целый корень
  int sqrtb;                 //  sqrtb целая часть корня из второго слагаемого 
  
  for (int i=1; i<=sqrta; i++){    //  проверка всех чисел от 1 до 5  на то что они корень из первого слагаемого, т.е.
                                // их квадрат это первое слагаемое в сумме  1 4 9 16 25
                                              //
     sqrtb=isqrt(arg-i*i);// i*i это первое слагаемое, тогда 25-i*i  это второе слагаемое, т.к. их сумма по условию 25
                             //    sqrtb целая часть корня из второго слагаемого (корень(25-i*i))
     if (sqrtb*sqrtb==arg-i*i)    //     если квадрат (целой части) корня числа - равен самому числу, 
                            //   значит из числа можно извлечь корень
        return true;  // тогда говорим, что да! число является суммой квадратов 
                          /// sqrtb*sqrtb+i*i=arg     (например 4*4+3*3=25)
   } 
  return false;        //если всё проверили и так и не нашли , говорим нет!
}
w0nder
0 / 0 / 0
Регистрация: 23.11.2012
Сообщений: 131
29.11.2012, 03:46  [ТС]     Спасайте х( Простое задание на функции, сумма квадратов чисел #5
А, и еще один вопрос. Что это за огромное наборы чисел в начале кода? И, они там обязательно должны быть?
Kuzia domovenok
1889 / 1744 / 117
Регистрация: 25.03.2012
Сообщений: 5,922
Записей в блоге: 1
29.11.2012, 03:57     Спасайте х( Простое задание на функции, сумма квадратов чисел #6
нет, не обязательно. Это быстрое извлечение целого квадратного корня. пожалуй можно удалить и заменить на простой sqrt()
Но мне понравилась эта необычная идея алгоритма!
Я нашёл его в интернете, но разобрался как это работает.
фактически это заранее заготовленный массив квадратов целых чисел. и поиск в этом массиве.
чтобы извлечь корень из х надо модифицированным бинарным поиском найти число х в этом массиве,
номер этого элемента и будет корнем из икс.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.11.2012, 04:03     Спасайте х( Простое задание на функции, сумма квадратов чисел
Еще ссылки по теме:
Найти все тройки чисел, сумма квадратов которых даёт заданное натуральное число C++
C++ Дан массив целых чисел. Верно ли, что сумма квадратов элементов массива есть пятизначное число
C++ Простое задание с AppWizard
Сумма квадратов ;) C++
C++ Определить двоичные числа из промежутка [a,b], сумма цифр которых - простое число

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

Или воспользуйтесь поиском по форуму:
w0nder
0 / 0 / 0
Регистрация: 23.11.2012
Сообщений: 131
29.11.2012, 04:03  [ТС]     Спасайте х( Простое задание на функции, сумма квадратов чисел #7
хм, а можно это как-то на sqrt заменить? а то мне код чем проще - тем лучше
Yandex
Объявления
29.11.2012, 04:03     Спасайте х( Простое задание на функции, сумма квадратов чисел
Ответ Создать тему
Опции темы

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