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

Функция проверки числа на полный квадрат

22.03.2016, 18:43. Просмотров 1521. Ответов 14
Метки нет (Все метки)

Небольшой вопросик:
Задание написать функцию проверки на полный квадрат.
Проблемма с условием.
(например число 5; ch = sqrt(5) ch = 2.236072, а число 9 будет ровно 3)
Не могу понять как у числа типа double сравнить остаток после запятой,
если оно равно нулю, то действие 1.
если нет то действие 2.

Большое спасибо.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.03.2016, 18:43
Ответы с готовыми решениями:

Полный квадрат числа
Определить, является ли заданно число полным квадратом!! double x;...

Функция проверки делимости числа на 8
Для проверки делимости числа на 8, необходимо, чтобы сумма цифр числа делилась...

Рекурсивная функция проверки простого числа
Не могу разобраться !! Как она вставляет в код без рекурсива?! Прошу помощи...

Функция проверки числа на простое значение
Описать функцию IsPrime(N) логического типа, возвращающую True, если целый...

Функция, возвращающая квадрат числа
создать функцию sqr(x), вычисляющую x*x; Используя ее, найти a^2+b^2+(a-b-1)^2

14
Hikari
Хитрая блондиночка $)
1451 / 963 / 399
Регистрация: 21.12.2015
Сообщений: 3,785
22.03.2016, 18:51 2
Лучший ответ Сообщение было отмечено SerJer как решение

Решение

Могу предложить из своей старой лабораторной:
C++
1
2
    double n=36;
    if(sqrt(n)-(int)sqrt(n)<0.001) printf("Квадрат"); else printf("Не очень чтобы квадрат");
Не ахти, но кураторов устраивало.
1
GbaLog-
Любитель чаепитий
3166 / 1472 / 465
Регистрация: 24.08.2014
Сообщений: 5,204
Записей в блоге: 1
Завершенные тесты: 2
22.03.2016, 18:58 3
Hikari, Кураторов, наверное, и такое устроит:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/////////////////////////////////////////////////////////////////////////////////////////
#include <iostream>
#include <cmath>
/////////////////////////////////////////////////////////////////////////////////////////
void f(double c)
{
    if(std::sqrt(c) == static_cast<int>(std::sqrt(c)))
    {
        std::cout << "square\n";
    }
    else
    {
        std::cout << "not square\n";
    }
}
/////////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::cout << "Hello, world!\n";
    f(10);
    f(9);
}
1
Байт
Эксперт C
18318 / 12029 / 2506
Регистрация: 24.12.2010
Сообщений: 24,293
22.03.2016, 19:34 4
Цитата Сообщение от SerJer Посмотреть сообщение
как у числа типа double сравнить остаток после запятой,
C++
1
2
double a, rest;
rest = fmod(a, 1.0);
1
Hikari
Хитрая блондиночка $)
1451 / 963 / 399
Регистрация: 21.12.2015
Сообщений: 3,785
22.03.2016, 20:33 5
Цитата Сообщение от GbaLog- Посмотреть сообщение
наверное, и такое устроит
Наверное
Если с хорошим коньяком преподнести
Кураторы это любят...
1
GbaLog-
22.03.2016, 20:38
  #6

Не по теме:

Hikari, Ох, взяточничество, я когда буду учится, точно не буду такого делать!!! Да и не придётся, с таким-то багажом знаний ещё до института. :^)
Хотя, по меркам С++, я очень мало знаю.

0
Hikari
22.03.2016, 22:06
  #7

Не по теме:

Цитата Сообщение от GbaLog- Посмотреть сообщение
я когда буду учится, точно не буду такого делать!
Ну ну... Пословицы мудрые говорят обратное.

0
SerJer
0 / 0 / 0
Регистрация: 18.10.2015
Сообщений: 37
23.03.2016, 02:31  [ТС] 8
Спасибо за помощь.
0
TheCalligrapher
С чаем беда...
Эксперт CЭксперт С++
4767 / 2426 / 677
Регистрация: 18.10.2014
Сообщений: 4,144
23.03.2016, 02:49 9
Лучший ответ Сообщение было отмечено ValeryS как решение

Решение

Целочисленная проверка на квадратность

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
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;
}
http://coliru.stacked-crooked.com/a/7ea326bff4717152
1
SpBerkut
Объявлятель переменных
948 / 274 / 276
Регистрация: 24.09.2011
Сообщений: 1,008
Завершенные тесты: 2
23.03.2016, 07:16 10
Лучший ответ Сообщение было отмечено ValeryS как решение

Решение

Ещё вариант с использованием только целочисленных операций. Без деления, к тому же.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool isSqr1(long long int x) {
    for (int i = 1; x > 0; x -= i, i+=2);
    return !x;
}
 
bool isSqr2(long long int x) {
    if (x&1) {
        x--;
        for (int i = 8; x > 0; x -= i, i+=8);
        return !x;
    }
    else {
        return ( x&3 ? false : isSqrt(x >> 2) );
    }
}
Обычно он работает дольше чем тот, который предложил TheCalligrapher, но квадраты больших простых чисел отлавливает быстрее. Например попробуйте проверить на "квадратность" число 440999958000001. Функция isSqr1 будет в 2 раза быстрее, а isSqr1 — в 4.
2
Байт
Эксперт C
18318 / 12029 / 2506
Регистрация: 24.12.2010
Сообщений: 24,293
23.03.2016, 10:24 11
TheCalligrapher, не понял, зачем выделять в отдельный блок делимость на 2.
Вот модифицированный ваш код
C++
1
2
3
4
5
6
7
8
9
for(d=2; n>1; d+=(d>2) ? 2 : 1) {
  flag = false;
  while (n%d==0) {
     flag = !flag;
     n /= d;
  }
  if (flag) return false;
}
return true;
Допускает и дальнейшую оптимизацию (копеечную) уменьшением количества "кандидатов в простые"
Хотя, возможно, еще лучше просто определять следующее простое число.
1
TheCalligrapher
С чаем беда...
Эксперт CЭксперт С++
4767 / 2426 / 677
Регистрация: 18.10.2014
Сообщений: 4,144
23.03.2016, 10:44 12
Цитата Сообщение от Байт Посмотреть сообщение
зачем выделять в отдельный блок делимость на 2.
Ну, например, затем, чтобы не делать проверку d > 2 на каждой итерации внешнего цикла, в то время как такая проверка фактически нужна только на первой его итерации. Не люблю такие циклы.

К тому же число 2 всегда стояло особняком среди простых чисел. Это единственное четное простое число. Его не грех и обработать особняком.

Цитата Сообщение от Байт Посмотреть сообщение
Хотя, возможно, еще лучше просто определять следующее простое число.
Если бы это было так просто!

Что можно сделать, так это выделить еще и число 3 в отдельный блок, а дальше воспользоваться тем фактом, что все простые числа, начиная с 5, имеют вид 6n-1 или 6n+1.
1
Байт
Эксперт C
18318 / 12029 / 2506
Регистрация: 24.12.2010
Сообщений: 24,293
23.03.2016, 11:17 13
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
К тому же число 2 всегда стояло особняком среди простых чисел. Это единственное четное простое число.
Ну, тогда и 3 стоит особняком. Это единственное простое число, делящееся на 3. Легко понять, что по этой логике все простые числа стоят особняком
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
Если бы это было так просто!
А чего сложного то?
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
а дальше воспользоваться тем фактом, что все простые числа, начиная с 5, имеют вид 6n-1 или 6n+1.
Полумеры какие-то...

Добавлено через 10 минут
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
p = 2;
while (n > 1) {
  flag = false;
  while (n%p==0) {
    flag = !flag;
    n /= p;
  }
  if (flag) return false;
  if (n==1) return true;
  for (p++, i=2; ; p++) {
     for(i=2; i*i<=p; i++)
        if (p%i==0)  break;
     if (i*i > p ) break;
  }
}
return true;
Не проверял. Но идея, надеюсь понятна.
2
TheCalligrapher
С чаем беда...
Эксперт CЭксперт С++
4767 / 2426 / 677
Регистрация: 18.10.2014
Сообщений: 4,144
23.03.2016, 20:11 14
Цитата Сообщение от Байт Посмотреть сообщение
Ну, тогда и 3 стоит особняком. Это единственное простое число, делящееся на 3. Легко понять, что по этой логике все простые числа стоят особняком
Совершенно верно. В теории, чем больше индивидуальных первых простых чисел вы поставите особняком и обработаете отдельно, тем более "точно" можно будет аппроксимировать последовательность простых чисел в оставшейся, общей части алгоритма.

Я отдельно обработал число 2. Что дало мне возможность аппроксимировать остаток последовательности простых чисел через последовательность нечетных чисел.

Если бы я отдельно обработал 2 и 3, то это дало бы мне возможность аппроксимировать остаток последовательности простых чисел через последовательность чисел вида 6n-+1.

Я решил, что для целей данного форума разумный баланс между компактностью и эффективностью кода пройдет как раз по первому варианту. Не более того.

Цитата Сообщение от Байт Посмотреть сообщение
А чего сложного то?
Цитата Сообщение от Байт Посмотреть сообщение
Но идея, надеюсь понятна.
Ну, здрасьте! Когда я говорил, что тестировать деление только на простые делители - непросто, я имел в виду то, что нет способа находить последовательные простые числа с эффективностью, достаточной для данного алгоритма (соразмерной с эффективностью основного алгоритма).

Вы предлагаете просто брутфорсно тестировать числа на простоту путем проверки делимости на все целые от 2 то корня из p? Да, конечно, таким способом вы найдете простые. Но эффективность основного алгоритм такой брутфорсовой "закладкой" будет угроблена напрочь.
1
SerJer
0 / 0 / 0
Регистрация: 18.10.2015
Сообщений: 37
31.03.2016, 06:55  [ТС] 15
Использовал вариант Hikari, саммый легкий, это главное на первом курсе, мало ли придется объеснить работу через месяц.

Спасибо всем !
0
31.03.2016, 06:55
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
31.03.2016, 06:55

Функция проверки числа на деление без остатка на другое число
Привет! Как организовать проверку числа на то делится ли оно без остатка или...

Сложная задача про полный квадрат
Есть 9 разных чисел a,b,c,d,e,f,g,h,i. Сумма любых двух разных чисел из данного...

Процедура: среди n чисел последовательности найти те, которые составляют полный квадрат
среди n чисел последовательности найти те которые составляют полный квадрат...


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

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

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