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

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

06.12.2012, 16:33. Показов 3748. Ответов 17

Можно ли заданное натуральное число М представить в виде суммы квадратов двух натуральных чисел? Написать программу решения этой задачи.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
06.12.2012, 16:33
Ответы с готовыми решениями:

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

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

Дано натуральное число n. Можно ли представить его в виде суммы трех квадратов натуральных чисел?
Подскажите как правильно составить программу к этим задачам: 1.Дано натуральное число n. Можно ли...

Определить, можно ли представить число в виде суммы двух квадратов натуральных чисел
Дано натуральное число n.Определить,можно ли представить его в виде суммы двух квадратов...

17
CEO SOVAZ Corp.
386 / 232 / 51
Регистрация: 17.12.2011
Сообщений: 822
Записей в блоге: 1
06.12.2012, 16:37 2
Типа 8 = 2^2 + 2^2???

Добавлено через 1 минуту
Сейчас займусь. Вроде понял, как делать)))
0
4003 / 3265 / 913
Регистрация: 25.03.2012
Сообщений: 12,192
Записей в блоге: 1
06.12.2012, 16:44 3
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;
}
0
4203 / 1795 / 211
Регистрация: 24.11.2009
Сообщений: 27,562
06.12.2012, 16:50 4
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
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
};
жёстко.
0
4003 / 3265 / 913
Регистрация: 25.03.2012
Сообщений: 12,192
Записей в блоге: 1
06.12.2012, 16:52 5
Цитата Сообщение от taras atavin Посмотреть сообщение
жёстко.
зато быстро.
Функция isqrt-целочисленный корень
это по сути оптимизированный бинарный поиск в этом массиве.
0
4203 / 1795 / 211
Регистрация: 24.11.2009
Сообщений: 27,562
06.12.2012, 16:53 6
А если корень - пара миллиардов?
0
CEO SOVAZ Corp.
386 / 232 / 51
Регистрация: 17.12.2011
Сообщений: 822
Записей в блоге: 1
06.12.2012, 16:55 7
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
#include <iostream>
#include <cmath>
 
using namespace std;
 
bool bin(double a);
 
int main()
{
    int n = 0;
 
    cin >> n;
 
    double past_n = n / 2;
 
    if(past_n < 1) {
        return 0;
    }
 
    if(bin(past_n)) {
        cout << sqrt(past_n) << "^2 + " << sqrt(past_n) << "^2";
    }
 
    else {
        cout << "Not value.";
    }
}
 
bool bin(double a) {
    for(int j = 1; j <= a; j = j * j ) {
        if(j == a) {
            return true;
        }
 
        if(j == 1) {
            j++;
        }
    }
 
    return false;
}
P.S. кпо меня услышит)))
0
1321 / 983 / 267
Регистрация: 17.05.2012
Сообщений: 2,687
06.12.2012, 16:58 8
sovaz1997 неправильно работает, попробуй число 13.
0
4003 / 3265 / 913
Регистрация: 25.03.2012
Сообщений: 12,192
Записей в блоге: 1
06.12.2012, 16:58 9
Цитата Сообщение от taras atavin Посмотреть сообщение
А если корень - пара миллиардов?
пара миллиардов в uint16 не влезет
И не забывай, что квадратные корень - медленная операция. Некоторые ЭВМ её секундами считали
0
CEO SOVAZ Corp.
386 / 232 / 51
Регистрация: 17.12.2011
Сообщений: 822
Записей в блоге: 1
06.12.2012, 16:59 10
Не все правильно у меня.
0
1321 / 983 / 267
Регистрация: 17.05.2012
Сообщений: 2,687
06.12.2012, 17:00 11
Предлагаю свой вариант
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
#include <iostream> 
#include <cmath>
 
int main() 
{ 
    int number; 
    double i, j;  
    bool flag = false; 
    std::cout << "Inter a number " << std::endl; 
    std::cin >> number;
 
    for ( i = 1; i < number/ 2; ++i)  
    {
        for ( j = 2; j < number / 2; ++j) 
            if(pow(i, 2) + pow(j, 2) == number)   
            {
               std::cout << "Yes " << i << " " << j << std::endl;  
               flag = true;
               break;
            } 
            if(flag)  
                break; 
    } 
    if(!flag) 
        std::cout << "No " << std::endl;
}
0
CEO SOVAZ Corp.
386 / 232 / 51
Регистрация: 17.12.2011
Сообщений: 822
Записей в блоге: 1
06.12.2012, 17:01 12
Надо создать двойной цикл. Попытаюсь исправить.
0
4003 / 3265 / 913
Регистрация: 25.03.2012
Сообщений: 12,192
Записей в блоге: 1
06.12.2012, 17:01 13
Цитата Сообщение от David Sylva Посмотреть сообщение
j = 2; j < number / 2
а что не до isqrt(number/2)
?
0
CEO SOVAZ Corp.
386 / 232 / 51
Регистрация: 17.12.2011
Сообщений: 822
Записей в блоге: 1
06.12.2012, 17:05 14
С векторами сделаю)))
0
4203 / 1795 / 211
Регистрация: 24.11.2009
Сообщений: 27,562
06.12.2012, 17:06 15
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
пара миллиардов в uint16 не влезет
Ну и что? Влезет в uint_32, а квадрат этого числа в hyper, он 64-х битный. 63 бита на само числа, 1 на знак, это более 8 000 000 000 000 000 000, а достаточно 4 000 000 000 000 000 000.
0
4003 / 3265 / 913
Регистрация: 25.03.2012
Сообщений: 12,192
Записей в блоге: 1
06.12.2012, 17:08 16
то, что автор не ограничил условиями задачи
эти... как..их...
Короче, это исключительно его проблемы
0
1321 / 983 / 267
Регистрация: 17.05.2012
Сообщений: 2,687
06.12.2012, 17:11 17
Kuzia domovenok Я поспешил поставить согласен, изложи в чём я не прав, не понял.
0
CEO SOVAZ Corp.
386 / 232 / 51
Регистрация: 17.12.2011
Сообщений: 822
Записей в блоге: 1
06.12.2012, 17:12 18
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
#include <iostream>
#include <cmath>
#include <vector>
 
using namespace std;
 
int main()
{
    int n = 0;
 
    cin >> n;
 
    vector<int>a;
 
    for(int i = 0; i < n; i++) {
        a.push_back(i * i);
    }
 
    for(int i = 0; i < a.size(); ++i) {
        for(int j = 0; j < a.size(); ++j) {
            if(a[i] + a[j] == n) {
                cout << i << "^2 + " << j << "^2";
 
                return 0;
            }
        }
    }
 
    cout << "No";
}
Вот теперь работает)))
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
06.12.2012, 17:12
Помогаю со студенческими работами здесь

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

Определить, можно ли заданное число представить в виде суммы двух квадратов
Задачка: можно ли заданное число представить в виде суммы двух квадратов. Решил вот так: ...

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

Можно ли заданное натуральное число М представить в виде суммы квадратов двух натуральных чисел?
1.Составить блок-схему &quot;Гороскоп&quot;(по месяцу выдает количество дней в месяце). 2. написать...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2023, CyberForum.ru