Форум программистов, компьютерный форум, киберфорум
Python: Решение задач
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.60/55: Рейтинг темы: голосов - 55, средняя оценка - 4.60
0 / 0 / 0
Регистрация: 15.04.2022
Сообщений: 1
1

Найти все числа на отрезке от А до B, которые являются полными квадратами

15.04.2022, 10:57. Показов 11387. Ответов 20

Author24 — интернет-сервис помощи студентам
Необходимо найти все числа на отрезке от А до B (А и B вводим) , которые являются полными квадратами. Если в заданном диапазоне таких чисел нет вывести -1.


Пример вводных данных и ответа :

Ввод : 1 30
Ответ : 1 4 9 16 25

Ввод : 10 50
Ответ : 16 25 36 49
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
15.04.2022, 10:57
Ответы с готовыми решениями:

Найти все трехзначные числа, которые являются полными квадратами и записываются тремя нечетными цифрами
Найти все трехзначные числа, которые являются полными квадратами и записываются тремя нечетными...

Найти все числа на отрезке от А до В являющиеся полными квадратами.
Найти все числа на отрезке от А до В являющиеся полными квадратами. например: ввод: 1 30...

Дан файл. Найти все компоненты, которые являются полными квадратами
Задание 2. Задан файл f компоненты которого являются целыми числами. Получите в файле g все...

Найти все числа, являющиеся полными квадратами, на заданном отрезке
Даны числа a и b. Необходимо найти все числа, являющиеся полными квадратами, на отрезке . Формат...

Найти количество чисел, которые не превосходят числа A и являются полными квадратами некоторого натурального числа
Найти количество чисел, которые не превосходят числа A и являются полными квадратами некоторого...

20
2170 / 1653 / 840
Регистрация: 10.01.2015
Сообщений: 5,192
15.04.2022, 11:57 2
Python
1
2
3
n, m = map( int, input('Введите 2 числа через пробел: ').split() )
res = [i for i in range(n, m+1) if i**0.5 == round(i**0.5)]
print(res if res else -1)
1
eaa
15.04.2022, 13:28
  #3

Не по теме:

Пифагор, медленно) можно быстрее же посчитать

0
2170 / 1653 / 840
Регистрация: 10.01.2015
Сообщений: 5,192
15.04.2022, 13:37 4
eaa, а почему "не по теме"? Полагаю, через циклы без range() и списка? Потому, что остануться только арифметические операции:
Python
1
2
3
4
while n <= m:
    if n**0.5 == round(n**0.5):
        print(n)
    n+=1
0
Эксперт Python
8592 / 4418 / 1855
Регистрация: 27.03.2020
Сообщений: 7,251
15.04.2022, 13:49 5
Пифагор,
Python
1
res = [i*i for i in range(ceil(n**.5), int(m**.5)+1)]
0
2170 / 1653 / 840
Регистрация: 10.01.2015
Сообщений: 5,192
15.04.2022, 14:00 6
Gdez, это получается быстрее? Тут и модуль подключается, и приведение к типу, и создание списка, и сам range(). Возможно, возможно. Я не замерял время выполнения, но сдается мне, цикл и чистая арифметика(не считая round()) - самое быстрое решение.
0
Эксперт Python
8592 / 4418 / 1855
Регистрация: 27.03.2020
Сообщений: 7,251
15.04.2022, 14:06 7
Пифагор,
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
import time
t1 = time.time()
from math import ceil
n, m = 1000000,2000000 #map( int, input('Введите 2 числа через пробел: ').split() )
res = [i*i for i in range(ceil(n**.5), int(m**.5)+1)]
print(time.time()-t1)
 
##########################
 
t2 = time.time()
n, m = 1000000, 2000000 #map( int, input('Введите 2 числа через пробел: ').split() )
res = [i for i in range(n, m+1) if i**0.5 == round(i**0.5)]
print(time.time()-t2)
1
2170 / 1653 / 840
Регистрация: 10.01.2015
Сообщений: 5,192
15.04.2022, 14:26 8
Gdez, а за счет чего код так быстро исполняется?
0
Эксперт Python
8592 / 4418 / 1855
Регистрация: 27.03.2020
Сообщений: 7,251
15.04.2022, 14:32 9
Пифагор, допустим диапазон = [1, 100]. Он содержит 10 полных квадратов. У меня счетчик цикла == 10. У Вас == 100
1
2170 / 1653 / 840
Регистрация: 10.01.2015
Сообщений: 5,192
15.04.2022, 14:42 10
Gdez, цифры увидел, но не совсем понял, как они формируются. В данном случае, 10 циклов вместо 100 получается из-за отсутствия ветвления и сравнения?
0
Эксперт Python
8592 / 4418 / 1855
Регистрация: 27.03.2020
Сообщений: 7,251
15.04.2022, 15:38 11
Пифагор,
ceil(n**.5) ^ 2 -> ближайший полный квадрат, больший "n"
int(m**.5) ^ 2 -> ближайший полный квадрат, меньший "m"
Соответственно квадраты чисел из диапазона [ceil(n**.5), int(m**.5)] и будут решением задачи
Как то так...
1
Модератор
Эксперт функциональных языков программированияЭксперт Python
37303 / 20737 / 4272
Регистрация: 12.02.2012
Сообщений: 34,131
Записей в блоге: 14
15.04.2022, 16:21 12
Не могу одобрить эти коды. Они используют плавающую точку, а значит для 16-и и более разрядных чисел начнут безбожно врать. Смотрите:

Python
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
def isSquare_1(x):
    if x in (0,1,4):
        return True
    a=1
    b=x//2
    while abs(a-b)>1:
        #print(a,b)
        c=(a+b)//2
        if c*c==x:
            return True
        elif c*c>x:
            b=c
        else:
            a=c
    else:
        return False
 
def isSquare_2(n):
    return n**0.5 == round(n**0.5)
 
x=1267650600228229401496703205376  # большое число
xx=x*x                                                    # его квадрат
xy=x*x-1                                                 # его квадрат-1 
 
print("Правильный тест:")
print(isSquare_1(xx))           # True
print(isSquare_1(xy))           # False
print("Неправильный тест:")            
print(isSquare_2(xx))           # True
print(isSquare_2(xy))           # True  !!!
3
enx
15.04.2022, 17:11
  #13

Не по теме:

Catstail, как всегда, чистая алгоритмическая магия :drink:

0
Status 418
Эксперт Python
4581 / 2348 / 602
Регистрация: 26.11.2017
Сообщений: 5,264
Записей в блоге: 3
15.04.2022, 22:59 14
Python
1
from math import isqrt
1
Модератор
Эксперт функциональных языков программированияЭксперт Python
37303 / 20737 / 4272
Регистрация: 12.02.2012
Сообщений: 34,131
Записей в блоге: 14
16.04.2022, 11:10 15
eaa, да... Но интересно же сделать самому.
0
Status 418
Эксперт Python
4581 / 2348 / 602
Регистрация: 26.11.2017
Сообщений: 5,264
Записей в блоге: 3
16.04.2022, 11:40 16
Catstail, полностью согласен. Но этот бин.поиск будет медленный. когда много чисел близких к 1018 из которых нужно корень вычислять. нужно другой писать, isqrt быстрый.
0
Модератор
Эксперт функциональных языков программированияЭксперт Python
37303 / 20737 / 4272
Регистрация: 12.02.2012
Сообщений: 34,131
Записей в блоге: 14
16.04.2022, 12:39 17
eaa, а есть более быстрые алгоритмы? Бин поиск - логарифмический.
0
Status 418
Эксперт Python
4581 / 2348 / 602
Регистрация: 26.11.2017
Сообщений: 5,264
Записей в блоге: 3
16.04.2022, 13:38 18
Catstail, если взять не икс пополам правую границу.

Добавлено через 51 минуту
проверил, оказывается нет разницы. но isqrt, в среднем работает в 3 раза быстрее.
1
Модератор
Эксперт функциональных языков программированияЭксперт Python
37303 / 20737 / 4272
Регистрация: 12.02.2012
Сообщений: 34,131
Записей в блоге: 14
16.04.2022, 14:00 19
eaa, а как он реализован? На Питоне?

Добавлено через 4 минуты
Есть еще идея - использовать классический метод Ньютона.
0
Status 418
Эксперт Python
4581 / 2348 / 602
Регистрация: 26.11.2017
Сообщений: 5,264
Записей в блоге: 3
16.04.2022, 14:37 20
модуль math, на си же.
Цитата Сообщение от Catstail Посмотреть сообщение
метод Ньютона
тот же бинпоиск.
0
16.04.2022, 14:37
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
16.04.2022, 14:37
Помогаю со студенческими работами здесь

Найти количество чисел, которые не превосходят числа A и являются полными квадратами некоторого натурального числа
Исходное задание: Найти количество чисел, которые не превосходят числа A и являются полными...

Найти произведение чисел, которые не превосходят 4000 и являются полными квадратами некоторого натурального числа
Найти произведение чисел, которые не превосходят 4000 и являются полными квадратами некоторого...

Есть ли совершенные числа из промежутка [2, n], которые являются полными квадратами
Число называется совершенным, если равно сумме всех своих делителей, кроме самого этого числа....

Выведите все числа на отрезке от a до b, являющиеся полными квадратами
Вводятся целые числа a и b. Гарантируется, что a не превосходит b. Выведите все числа на отрезке...

Найдите все числа, являющиеся полными квадратами, на отрезке от A до B
Найдите все числа на отрезке от A до B, являющиеся полными квадратами


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru