Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 5.00/7: Рейтинг темы: голосов - 7, средняя оценка - 5.00
8 / 7 / 1
Регистрация: 08.04.2021
Сообщений: 151

Корень числа

03.08.2022, 21:59. Показов 1918. Ответов 30
Метки c++, с++ (Все метки)

Студворк — интернет-сервис помощи студентам
Дано 0 <= n <= 264 - 1, нужно с помощью бинарного поиска найти целую часть корня n
На мой код система говорит WA. Пожалуйста помогите
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
#include <iostream>
#include <cmath>
#include<vector>
#include<algorithm>
using namespace std;
 
int main() {
    //int n; cin >> n;
    //for (int h = 0; h < n; h++) {
    long long x;
    while (cin >> x) {
        long long m, l = -1, r = x + 1;
        while (r - l > 1)
        {
            m = (l + r) / 2;
            if (m*m - x <= 0)
                l = m;
            else
                r = m;
        }
        cout << l << endl;
    }
    return 0;
}
Добавлено через 50 секунд
264 это 264
0
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
03.08.2022, 21:59
Ответы с готовыми решениями:

Даны два числа. Если квадратный корень из второго числа меньше первого числа, то увеличить второе число в пять раз
Даны два числа. Если квадратный корень из второго числа меньше первого числа, то увличить второе число в пять раз с++ Добавлено через...

Вставить после числа, являющегося полным квадратом, квадратный корень этого числа
Вставить после числа, являющегося полным квадратом, квадратный корень этого числа. Вообще не понимаю как это написать в Си( ...

Для каждого числа найти корень квадратный, если дробная часть меньше 5, в противном случае найти квадрат данного числа
Даны три положительные действительные числа. Для каждого числа найти корень квадратный, если дробная часть меньше 5, в противном случае...

30
 Аватар для programmer_08
687 / 444 / 209
Регистрация: 18.10.2020
Сообщений: 1,606
04.08.2022, 13:37
Студворк — интернет-сервис помощи студентам
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
#include <iostream>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <ctime>
#pragma warning(disable: 4996)
 
uintmax_t find(uintmax_t x)
{
    if(x == 1)
        return 1;
    uintmax_t left = x / 2, right = x;
    
    while (true)
        if(float(left) * left > x)
        {
            right = left;
            left /= 2;
        }
        else
            if(float(left) * left != x && float(left + 1) * (left + 1) <= x)
                left += (right - left) / 2;
            else return left;
}
 
#define MAX_ROOTABLE_64 0xFFFFFFFE00000001LL // 4294967295? = 0xFFFFFFFF?
#define SQ(x) ((x) * (x))
 
// íàõîæäåíèå öåëîé ÷àñòè êâ. êîðíÿ
uint64_t root(uint64_t x)
{
  // âûðîæäåííûé ñëó÷àé
  if (x >= MAX_ROOTABLE_64)
    return UINT_MAX;
 
  // îñíîâíîé àëãîðèòì
  uint64_t mid, left = 0, right = x > UINT_MAX ? UINT_MAX : x;
  do
  {
    mid = (left + right) >> 1;
    if (SQ(mid) == x) return mid;
    if (SQ(mid) <= x) left  = mid;
    else              right = mid;
  } while (right - left > 1);
 
  return left;
}
 
int main()
{
    float X;
    while (std::cin >> X)
    {
        while(std::cin.get() != '\n');
        if(X > 0)
        {
            uintmax_t res;
            time_t start = clock();
            //for(int i = 0; i < 1000000; i++)
                res = root(X);//используя вашу функцию
            time_t finish = clock();
            if(res == 0)
                res = UINT_MAX;
            printf("time: %d   result: %llu   difference: %g\n", finish - start, res, sqrt(X) - res);
        }
        else
            printf("Please, input someth better then 0 next time\n");
    }
    return 0;
}
Миниатюры
Корень числа  
0
 Аватар для programmer_08
687 / 444 / 209
Регистрация: 18.10.2020
Сообщений: 1,606
04.08.2022, 13:38
а не стоп) видать в прошлый раз я что-то не так скопировал или вставил)
0
Злостный нарушитель
 Аватар для Verevkin
10916 / 5844 / 1289
Регистрация: 12.03.2015
Сообщений: 26,951
04.08.2022, 13:42
Цитата Сообщение от programmer_08 Посмотреть сообщение
пробовал)
Ну и чо тебя не устраивает?
4294967295 - это и есть 232-1.

Кликните здесь для просмотра всего текста


Добавлено через 2 минуты
Цитата Сообщение от programmer_08 Посмотреть сообщение
а не стоп) видать в прошлый раз я что-то не так скопировал или вставил)
Ты б, хоть, в консоли нормальный шрифт поставил, ёмаё. Глаза вытекут нах.
0
 Аватар для programmer_08
687 / 444 / 209
Регистрация: 18.10.2020
Сообщений: 1,606
04.08.2022, 13:54
ну в любом случае, допустим для такого числа: 18446744000000000000, оно даёт ответ на фото (2^32 - 1, что с вашим кодом, что с моим)... а должно быть: 42949672887
Миниатюры
Корень числа  
0
Злостный нарушитель
 Аватар для Verevkin
10916 / 5844 / 1289
Регистрация: 12.03.2015
Сообщений: 26,951
04.08.2022, 14:02
Цитата Сообщение от programmer_08 Посмотреть сообщение
а должно быть: 42949672887
Да блин, чувак, ну что с тобой не так, а?
Переставь руки в плечи, штоли...



Это целочисленная задача. Решать её с применением функций с плавающей точкой не имеет смысла.
0
 Аватар для programmer_08
687 / 444 / 209
Регистрация: 18.10.2020
Сообщений: 1,606
04.08.2022, 14:05
Verevkin, а можно тогда весь код, а то видать руки из одного места, что даже скопировать и вставить не получается?)
0
Злостный нарушитель
 Аватар для Verevkin
10916 / 5844 / 1289
Регистрация: 12.03.2015
Сообщений: 26,951
04.08.2022, 14:08
Цитата Сообщение от programmer_08 Посмотреть сообщение
а можно тогда весь код
Дарю:
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
#include <cstdio>
#include <cstdint>
#include <cmath>
#include <climits>
 
#define MAX_ROOTABLE_64 0xFFFFFFFE00000001LL // 4294967295² = 0xFFFFFFFF²
#define SQ(x) ((x) * (x))
 
// нахождение целой части кв. корня
uint64_t root(uint64_t x)
{
  // вырожденный случай
  if (x >= MAX_ROOTABLE_64)
    return UINT_MAX;
 
  // основной алгоритм
  uint64_t mid, left = 0, right = x > UINT_MAX ? UINT_MAX : x;
  do
  {
    mid = (left + right) >> 1;
    if (SQ(mid) == x) return mid;
    if (SQ(mid) <= x) left  = mid;
    else              right = mid;
  } while (right - left > 1);
 
  return left;
}
 
int main()
{
  uint64_t x[] =
  {
    1, 2, 3, 4, 5,
    1237,
    1225,
    1224,
    31476239184LL,
    0xFFFFFFFFFFFFFFFFLL,
    0xFFFFFFFE00000001LL,
    0xFFFFFFFE00000000LL,
    18446744000000000000LL,
    0LL // end
  };
  auto ptr = x;
  do printf("root(%lu) = %lu\n", *ptr, root(*ptr));
   //printf("root(0x%llX) = 0x%llX\n", *ptr, root(*ptr));
  while (*ptr++);
  getchar();
  return EXIT_SUCCESS;
}
Цитата Сообщение от programmer_08 Посмотреть сообщение
а то видать руки из одного места, что даже скопировать и вставить не получается
1
 Аватар для programmer_08
687 / 444 / 209
Регистрация: 18.10.2020
Сообщений: 1,606
04.08.2022, 14:09
Verevkin, благодарю!)
0
Злостный нарушитель
 Аватар для Verevkin
10916 / 5844 / 1289
Регистрация: 12.03.2015
Сообщений: 26,951
04.08.2022, 14:16
Цитата Сообщение от programmer_08 Посмотреть сообщение
благодарю!)
Вот так - немного покомпактнее:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// нахождение целой части кв. корня
uint64_t root(uint64_t x)
{
  // вырожденный случай
  if (x >= MAX_ROOTABLE_64) return UINT_MAX;
 
  // основной алгоритм
  uint64_t mid, left = 0, right = x > UINT_MAX ? UINT_MAX : x;
  
  do
  {
    mid = (left + right) >> 1;
    if (SQ(mid) == x) return mid; // точный корень
    (SQ(mid) < x ? left : right) = mid;
  } while (right - left > 1);
 
  return left;
}
0
 Аватар для programmer_08
687 / 444 / 209
Регистрация: 18.10.2020
Сообщений: 1,606
04.08.2022, 14:19
и ещё наверное нужно добавить
C++
1
if(x == 1) return 1;
и в printf() нужно всё же %llu (у меня просто %lu - это 4 байта)
0
Злостный нарушитель
 Аватар для Verevkin
10916 / 5844 / 1289
Регистрация: 12.03.2015
Сообщений: 26,951
04.08.2022, 14:22
Цитата Сообщение от programmer_08 Посмотреть сообщение
и в printf() нужно всё же %llu (у меня просто %lu - это 4 байта)
У меня 64-битный компилятор gcc/g++.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
04.08.2022, 14:22

Квадратный корень числа
Найдите квадратный корень числа, введенного с клавиатуры! С++

Квадратный корень числа
(С++ на Visual) Мне нужно решить довольно большой пример и в нем есть квадратный корень и с ним начелась проблема.Я знаю что нужен sqrt...

Корень из целого числа.
Здравствуйте, решал вот эту задачу. Написал следующий код: #include &lt;iostream&gt; #include &lt;math.h&gt; using namespace std; int...

Вычислить корень из числа.
//--------------------------------------------------------------------------- #pragma hdrstop #include &lt;tchar.h&gt; #include...

Получить корень из числа
Всем привет. К примеру такой код #include&lt;iostream&gt; #include&lt;math.h&gt; #include&lt;stdlib.h&gt;


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

Или воспользуйтесь поиском по форуму:
31
Ответ Создать тему
Новые блоги и статьи
Особенности gif сгенерированных в Си
russiannick 21.10.2026
Рассмотрим генерацию gif файлов, которые в Си имеют свои особенности. Gif представляет собой графический формат популярный в интернете. Посмотрим на палитру. Gif файл сгенерированный в си отличается. . .
FPS контроллер с анимированными Y-Bot и 3D-звуком miniaudio (Box3D, Recast, BehaviorTree.CPP, ozz-animation, ImGui, OpenGL и SDL3)
8Observer8 18.10.2026
Содержание блога | English Version Полное мультиплатформенное руководство по стартовому проекту с FPS-контроллером игрока, анимированными роботами Y-Bot с 4-слойным блендингом, 3D-физикой Box3D,. . .
Локальный http сервер
Argus19 17.10.2026
Локальный http сервер На работе, на двух локальных компьютерах круглосуточно работают программы опроса приборов с записью в книги Excel,которые раз в сутки записываются на сервер компании. Т. к. . . .
Копировать Windows на новый диск на UEFI
damix 17.10.2026
https:/ / uriesk. wordpress. com/ 2016/ 11/ 01/ move-window-10-to-ssd-on-a-uefi-dualboot-system-with-basic-linux-tools/ TL DR Вставляем диск, а старый подключаем через переходник, грузимся с лайва. . .
ИИ не может найти нужный язык в списке
Supersumestria 05.10.2026
Я ему даю вот такое изображение и прошу найти и подчеркнуть немецкий язык. Возвращает он вот это: https:/ / i. **********/ vqBWLe2. png Нужную строчку в 3й колонке просто выдумал. . Это. . .
Новая последняя моя музыка в SUNO
zorxor 05.10.2026
Здравствуйте, дорогие мои друзья! С большой радостью я хотел бы представить вам свою новую последнею музыку, которую сгенерировала мне по моей просьбе нейросеть SUNO. С уважением, zorxor. Это. . .
Программный домашний кинотеатр
russiannick 27.09.2026
Сподобился на программный домашний кинотеатр. В качестве ЯВУ по традиции выбрал js. В помощники взял Яндекс-Алису. Было создано три зала на разные интересы. исторические и ретро сериал Хичкок. . .
Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого
zorxor 21.09.2026
Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru