Найти минимальные и максимальные n-значные квадраты и кубы (Python, C++, JavaScript)
К чему стремимся
В этой статье показано, как для заданного целого n найти:
- наименьшее n-значное число, являющееся совершенным квадратом;
- наибольшее n-значное число, являющееся совершенным квадратом;
- аналогично — для совершенных кубов.
Даны готовые программы на C++, Python и JavaScript и типичные результаты для n = 1..4. Также обсуждаются сценарии, когда подход с плавающей точкой может дать неверный результат, и приводятся альтернативы.
Основная идея и формулы
Определение: совершенный квадрат — это целое m^2, совершенный куб — m^3.
Пусть n — количество цифр. Диапазон n-значных чисел: [10^(n-1), 10^n - 1].
- Минимальный n-значный совершенный квадрат: pow(ceil(sqrt(pow(10, n - 1))), 2)
- Максимальный n-значный совершенный квадрат: pow(ceil(sqrt(pow(10, n))) - 1, 2)
Для кубов заменяем sqrt на cbrt и степень 2 на 3:
- Минимальный n-значный совершенный куб: pow(ceil(cbrt(pow(10, n - 1))), 3)
- Максимальный n-значный совершенный куб: pow(ceil(cbrt(pow(10, n))) - 1, 3)
Важно: эти формулы используют взятие корня и округление вверх. На практике при больших n возможны погрешности из-за арифметики с плавающей точкой — см. раздел «Погрешности и альтернативы».
Примеры и готовые программы
Ниже — оригинальные примеры на C++, Python и JavaScript. Код сохранён в исходном виде.
C++: квадраты
`// C++ program to find the smallest and largest
// n-digit perfect squares
#include
using namespace std;
void findPerfectSquares(int n)
{
cout << "Smallest "<< n << "-digit perfect square: " << pow(ceil(sqrt(pow(10, n - 1))), 2) << endl;
cout << "Largest " << n << "-digit perfect square: " << pow(ceil(sqrt(pow(10, n))) - 1, 2) << endl;
}
int main()
{
int n1 = 1;
cout << "Number of digits: " << n1 << endl;
findPerfectSquares(n1);
int n2 = 2;
cout << "Number of digits: " << n2 << endl;
findPerfectSquares(n2);
int n3 = 3;
cout << "Number of digits: " << n3 << endl;
findPerfectSquares(n3);
int n4 = 4;
cout << "Number of digits: " << n4 << endl;
findPerfectSquares(n4);
return 0;
}`
Ожидаемый вывод:
`Number of digits: 1
Smallest 1-digit perfect square: 1
Largest 1-digit perfect square: 9
Number of digits: 2
Smallest 2-digit perfect square: 16
Largest 2-digit perfect square: 81
Number of digits: 3
Smallest 3-digit perfect square: 100
Largest 3-digit perfect square: 961
Number of digits: 4
Smallest 4-digit perfect square: 1024
Largest 4-digit perfect square: 9801
`
Python: квадраты
`# Python program to find the smallest and largest
# n-digit perfect squares
import math
def findPerfectSquares(n):
print("Smallest ", n,"-digit perfect square:", pow(math.ceil(math.sqrt(pow(10, n - 1))), 2))
print("Largest ", n,"-digit perfect square:", pow(math.ceil(math.sqrt(pow(10, n))) - 1, 2))
n1 = 1
print("Number of digits:", n1)
findPerfectSquares(n1)
n2 = 2
print("Number of digits:", n2)
findPerfectSquares(n2)
n3 = 3
print("Number of digits:", n3)
findPerfectSquares(n3)
n4 = 4
print("Number of digits:", n4)
findPerfectSquares(n4)`
Ожидаемый вывод:
`Number of digits: 1
Smallest 1 -digit perfect square: 1
Largest 1 -digit perfect square: 9
Number of digits: 2
Smallest 2 -digit perfect square: 16
Largest 2 -digit perfect square: 81
Number of digits: 3
Smallest 3 -digit perfect square: 100
Largest 3 -digit perfect square: 961
Number of digits: 4
Smallest 4 -digit perfect square: 1024
Largest 4 -digit perfect square: 9801
`
JavaScript: квадраты
`// JavaScript program to find the smallest and largest
// n-digit perfect squares
function findPerfectSquares(n) {
document.write("Smallest " + n + "-digit perfect square: " + Math.pow(Math.ceil(Math.sqrt(Math.pow(10, n - 1))), 2) + " ");
document.write("Largest " + n + "-digit perfect square: " + Math.pow(Math.ceil(Math.sqrt(Math.pow(10, n))) - 1, 2) + " ");
}
var n1 = 1;
document.write("Number of digits: " + n1 + " ");
findPerfectSquares(n1);
var n2 = 2;
document.write("Number of digits: " + n2 + " ");
findPerfectSquares(n2);
var n3 = 3;
document.write("Number of digits: " + n3 + " ");
findPerfectSquares(n3);
var n4 = 4;
document.write("Number of digits: " + n4 + " ");
findPerfectSquares(n4);`
Ожидаемый вывод:
`Number of digits: 1
Smallest 1-digit perfect square: 1
Largest 1-digit perfect square: 9
Number of digits: 2
Smallest 2-digit perfect square: 16
Largest 2-digit perfect square: 81
Number of digits: 3
Smallest 3-digit perfect square: 100
Largest 3-digit perfect square: 961
Number of digits: 4
Smallest 4-digit perfect square: 1024
Largest 4-digit perfect square: 9801`
Кубы: описание и примеры
Заменяем sqrt на cbrt и степень 2 на 3 — остальной подход тот же.
C++: кубы
`// C++ program to find the smallest and largest
// n-digit perfect cubes
#include
using namespace std;
void findPerfectCubes(int n)
{
cout << "Smallest "<< n << "-digit perfect cube: " << pow(ceil(cbrt(pow(10, (n - 1)))), 3) << endl;
cout << "Largest " << n << "-digit perfect cube: " << (int)pow(ceil(cbrt(pow(10, (n)))) - 1, 3) << endl;
}
int main()
{
int n1 = 1;
cout << "Number of digits: " << n1 << endl;
findPerfectCubes(n1);
int n2 = 2;
cout << "Number of digits: " << n2 << endl;
findPerfectCubes(n2);
int n3 = 3;
cout << "Number of digits: " << n3 << endl;
findPerfectCubes(n3);
int n4 = 4;
cout << "Number of digits: " << n4 << endl;
findPerfectCubes(n4);
return 0;
}`
Ожидаемый вывод:
`Number of digits: 1
Smallest 1-digit perfect cube: 1
Largest 1-digit perfect cube: 8
Number of digits: 2
Smallest 2-digit perfect cube: 27
Largest 2-digit perfect cube: 64
Number of digits: 3
Smallest 3-digit perfect cube: 125
Largest 3-digit perfect cube: 729
Number of digits: 4
Smallest 4-digit perfect cube: 1000
Largest 4-digit perfect cube: 9261`
Python: кубы
`# Python program to find the smallest and largest
# n-digit perfect cubes
import math
def findPerfectCubes(n):
print("Smallest ", n,"-digit perfect cube:", pow(math.ceil((pow(10, (n - 1))) (1 / 3)), 3) )
print("Largest ", n,"-digit perfect cube:", pow(math.ceil((pow(10, (n))) (1 / 3)) - 1, 3))
n1 = 1
print("Number of digits:", n1)
findPerfectCubes(n1)
n2 = 2
print("Number of digits:", n2)
findPerfectCubes(n2)
n3 = 3
print("Number of digits:", n3)
findPerfectCubes(n3)
n4 = 4
print("Number of digits:", n4)
findPerfectCubes(n4)`
Ожидаемый вывод:
`Number of digits: 1
Smallest 1 -digit perfect cube: 1
Largest 1 -digit perfect cube: 8
Number of digits: 2
Smallest 2 -digit perfect cube: 27
Largest 2 -digit perfect cube: 64
Number of digits: 3
Smallest 3 -digit perfect cube: 125
Largest 3 -digit perfect cube: 729
Number of digits: 4
Smallest 4 -digit perfect cube: 1000
Largest 4 -digit perfect cube: 9261`
JavaScript: кубы
`// JavaScript program to find the smallest and largest
// n-digit perfect cubes
function findPerfectCubes(n) {
document.write("Smallest " + n + "-digit perfect cube: " + Math.pow(Math.ceil(Math.cbrt(Math.pow(10, (n - 1)))), 3) + " ");
document.write("Largest " + n + "-digit perfect cube: " + Math.pow(Math.ceil(Math.cbrt(Math.pow(10, (n)))) - 1, 3) + " ");
}
var n1 = 1;
document.write("Number of digits: " + n1 + " ");
findPerfectCubes(n1);
var n2 = 2;
document.write("Number of digits: " + n2 + " ");
findPerfectCubes(n2);
var n3 = 3;
document.write("Number of digits: " + n3 + " ");
findPerfectCubes(n3);
var n4 = 4;
document.write("Number of digits: " + n4 + " ");
findPerfectCubes(n4);`
Ожидаемый вывод:
`Number of digits: 1
Smallest 1-digit perfect cube: 1
Largest 1-digit perfect cube: 8
Number of digits: 2
Smallest 2-digit perfect cube: 27
Largest 2-digit perfect cube: 64
Number of digits: 3
Smallest 3-digit perfect cube: 125
Largest 3-digit perfect cube: 729
Number of digits: 4
Smallest 4-digit perfect cube: 1000
Largest 4-digit perfect cube: 9261`
Погрешности и когда подход может дать неверный результат
Important: Формулы с использованием sqrt/cbrt и pow опираются на арифметику с плавающей точкой. Для достаточно больших n погрешности округления могут привести к ошибочному значению ceil(sqrt(…)).
Когда возникает проблема:
- n очень большое (например, десятки тысяч цифр) — величины 10^n не помещаются в типы с плавающей точкой;
- стандартная библиотека возвращает немного меньшее или большее значение корня из-за ограниченной точности.
Простой симптом: результат возвращает число, которое не имеет ровно n цифр или не является точным квадратом/кубом.
Альтернативные подходы (без плавающей точки)
Целочисленный поиск корня методом бинарного поиска. Идея: найти минимальное m такое, что m^2 >= 10^(n-1). При этом все вычисления выполняются в целых (big integers) — в Python это нативно, в C++ нужно использовать библиотеки big integer.
Работа с логарифмами в высокой точности (Decimal или BigDecimal) и аккуратное округление.
Для сравнительно небольших n (до ~15–17 цифр) безопасно использовать 64-битовые целые и проверять результат через целочисленное возведение в степень.
Пример псевдокода целочисленного поиска минимального квадрата:
- left = 1, right = 10^ceil(n/2)
- while left < right:
- mid = (left + right) // 2
- if mid*mid >= 10^(n-1): right = mid
- else left = mid + 1
- ответ = left*left
Этот метод надёжен при наличии bigint.
Быстрые эвристики и ментальные модели
- Число цифр квадрата m^2 примерно равно 2 (число цифр m) или 2 floor(log10(m)) + 1.
- Чтобы получить n цифр у квадрата, корень m обычно имеет примерно ceil(n/2) цифр.
- Для кубов корень имеет примерно ceil(n/3) цифр.
Критерии приёмки
- Для любого тестового n функция возвращает число с ровно n цифрами.
- Результат действительно является совершенным квадратом/кубом.
- Алгоритм корректен для разумных границ n (определите SLA: до 18 цифр для 64-битных типов, для больших — используйте bigint).
Тест-кейсы (примеры для автоматизированного тестирования)
- n = 1 → квадраты: min=1, max=9; кубы: min=1, max=8.
- n = 2 → квадраты: min=16, max=81; кубы: min=27, max=64.
- n = 3 → квадраты: min=100, max=961; кубы: min=125, max=729.
- n = 0 или n < 1 → ошибка/исключение (определите поведение API).
- Большие n (например, n=1000) → проверять, используется ли bigint и что время выполнения приемлемо.
Role-based checklist
- Для разработчика: покрыть edge-cases, добавить проверки входа, выбрать bigint для больших n.
- Для преподавателя: подготовить примеры с визуализацией корней и диапазонов, объяснить связь числа цифр и порядка корня.
- Для собеседующего: попросить реализовать оба варианта — через float и через целочисленный бинарный поиск — и сравнить их.
Краткое резюме
- Формулы на основе ceil(sqrt(…)) и ceil(cbrt(…)) работают быстро и просто для небольших n.
- Для больших n используйте целочисленные методы с bigint или высокоточные типы, чтобы избежать ошибок из‑за округления.
- Примеры на C++, Python и JavaScript доступны выше и демонстрируют работу для n = 1..4.
Заметки: решая подобные задачи, всегда указывайте ограничения на входные данные (максимальное n) и тестируйте граничные случаи.
Автор
Редакция
Похожие материалы
Android.
Виджет Google Tasks на Android — быстрый гайд
Windows 11
Запуск Sticky Notes при включении Windows 11
Windows
Как исправить WDF_Violation в Windows
Загрузчик
Добавить Windows 11 в меню GRUB
Microsoft Word
Удаление колонтитулов в Word — быстрое руководство
Windows