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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 4.60
кпо
0 / 0 / 0
Регистрация: 02.12.2012
Сообщений: 21
06.12.2012, 16:33     Можно ли заданное натуральное число М представить в виде суммы квадратов двух натуральных чисел? #1
Можно ли заданное натуральное число М представить в виде суммы квадратов двух натуральных чисел? Написать программу решения этой задачи.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.12.2012, 16:33     Можно ли заданное натуральное число М представить в виде суммы квадратов двух натуральных чисел?
Посмотрите здесь:

можно ли заданное число представить в виде суммы двух квадратов C++
Среди чисел найти все те, которые можно представить в виде суммы квадратов двух натуральных чисел C++
C++ Можно ли число C представить как разность квадратов двух натуральных чисел?
C++ Дано натуральное число n. Можно ли представить его в виде суммы трех квадратов натуральных чисел?
C++ Даны натуральное число n. Среди чисел 1, 2, …, n найти все те, которые можно представить в виде суммы квадратов двух натуральных чисел.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
sovaz1997
CEO SOVAZ Corp.
 Аватар для sovaz1997
379 / 225 / 2
Регистрация: 17.12.2011
Сообщений: 816
Записей в блоге: 1
06.12.2012, 16:37     Можно ли заданное натуральное число М представить в виде суммы квадратов двух натуральных чисел? #2
Типа 8 = 2^2 + 2^2???

Добавлено через 1 минуту
Сейчас займусь. Вроде понял, как делать)))
Kuzia domovenok
 Аватар для Kuzia domovenok
1883 / 1738 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 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;
}
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
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
};
жёстко.
Kuzia domovenok
 Аватар для Kuzia domovenok
1883 / 1738 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
06.12.2012, 16:52     Можно ли заданное натуральное число М представить в виде суммы квадратов двух натуральных чисел? #5
Цитата Сообщение от taras atavin Посмотреть сообщение
жёстко.
зато быстро.
Функция isqrt-целочисленный корень
это по сути оптимизированный бинарный поиск в этом массиве.
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
06.12.2012, 16:53     Можно ли заданное натуральное число М представить в виде суммы квадратов двух натуральных чисел? #6
А если корень - пара миллиардов?
sovaz1997
CEO SOVAZ Corp.
 Аватар для sovaz1997
379 / 225 / 2
Регистрация: 17.12.2011
Сообщений: 816
Записей в блоге: 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. кпо меня услышит)))
David Sylva
 Аватар для David Sylva
1281 / 943 / 51
Регистрация: 17.05.2012
Сообщений: 2,686
06.12.2012, 16:58     Можно ли заданное натуральное число М представить в виде суммы квадратов двух натуральных чисел? #8
sovaz1997 неправильно работает, попробуй число 13.
Kuzia domovenok
 Аватар для Kuzia domovenok
1883 / 1738 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
06.12.2012, 16:58     Можно ли заданное натуральное число М представить в виде суммы квадратов двух натуральных чисел? #9
Цитата Сообщение от taras atavin Посмотреть сообщение
А если корень - пара миллиардов?
пара миллиардов в uint16 не влезет
И не забывай, что квадратные корень - медленная операция. Некоторые ЭВМ её секундами считали
sovaz1997
CEO SOVAZ Corp.
 Аватар для sovaz1997
379 / 225 / 2
Регистрация: 17.12.2011
Сообщений: 816
Записей в блоге: 1
06.12.2012, 16:59     Можно ли заданное натуральное число М представить в виде суммы квадратов двух натуральных чисел? #10
Не все правильно у меня.
David Sylva
 Аватар для David Sylva
1281 / 943 / 51
Регистрация: 17.05.2012
Сообщений: 2,686
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;
}
sovaz1997
CEO SOVAZ Corp.
 Аватар для sovaz1997
379 / 225 / 2
Регистрация: 17.12.2011
Сообщений: 816
Записей в блоге: 1
06.12.2012, 17:01     Можно ли заданное натуральное число М представить в виде суммы квадратов двух натуральных чисел? #12
Надо создать двойной цикл. Попытаюсь исправить.
Kuzia domovenok
 Аватар для Kuzia domovenok
1883 / 1738 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
06.12.2012, 17:01     Можно ли заданное натуральное число М представить в виде суммы квадратов двух натуральных чисел? #13
Цитата Сообщение от David Sylva Посмотреть сообщение
j = 2; j < number / 2
а что не до isqrt(number/2)
?
sovaz1997
CEO SOVAZ Corp.
 Аватар для sovaz1997
379 / 225 / 2
Регистрация: 17.12.2011
Сообщений: 816
Записей в блоге: 1
06.12.2012, 17:05     Можно ли заданное натуральное число М представить в виде суммы квадратов двух натуральных чисел? #14
С векторами сделаю)))
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
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.
Kuzia domovenok
 Аватар для Kuzia domovenok
1883 / 1738 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
06.12.2012, 17:08     Можно ли заданное натуральное число М представить в виде суммы квадратов двух натуральных чисел? #16
то, что автор не ограничил условиями задачи
эти... как..их...
Короче, это исключительно его проблемы
David Sylva
 Аватар для David Sylva
1281 / 943 / 51
Регистрация: 17.05.2012
Сообщений: 2,686
06.12.2012, 17:11     Можно ли заданное натуральное число М представить в виде суммы квадратов двух натуральных чисел? #17
Kuzia domovenok Я поспешил поставить согласен, изложи в чём я не прав, не понял.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.12.2012, 17:12     Можно ли заданное натуральное число М представить в виде суммы квадратов двух натуральных чисел?
Еще ссылки по теме:

Даны натуральное число n. Среди чисел 1, 2, …, n найти все те, которые можно представить в виде суммы квадратов двух натуральных чисел C++
Вывести наименьшее натуральное число, которое можно представить двумя разными способами в виде суммы кубов двух натуральных чисел C++
Определить, можно ли представить число в виде суммы двух квадратов натуральных чисел C++

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

Или воспользуйтесь поиском по форуму:
sovaz1997
CEO SOVAZ Corp.
 Аватар для sovaz1997
379 / 225 / 2
Регистрация: 17.12.2011
Сообщений: 816
Записей в блоге: 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";
}
Вот теперь работает)))
Yandex
Объявления
06.12.2012, 17:12     Можно ли заданное натуральное число М представить в виде суммы квадратов двух натуральных чисел?
Ответ Создать тему

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

Текущее время: 07:02. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru