Наименьшие и наибольшие n-значные квадраты и кубы

Содержание

• Квадраты: условие, подход, примеры и коды
• Кубы: условие, подход, примеры и коды
• Когда подходы дают сбой и альтернативы
• Тесты, критерии приёмки и чек-листы

Квадраты: наименьшие и наибольшие n-значные числа

Условие задачи

Дано целое n. Нужно найти наименьшее и наибольшее n-значное число, которое является точным квадратом (k^2 для целого k).

Примеры:

• n = 2: наименьший 2-значный квадрат — 16, наибольший — 81.
• n = 3: наименьший 3-значный квадрат — 100, наибольший — 961.

Подход

Если число имеет 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)

Формулы дают целое k = ceil(sqrt(10^(n-1))) для наименьшего квадрата и k = ceil(sqrt(10^n)) - 1 для наибольшего.

Важно: для малых n формулы точны; для очень больших n возможны ошибки округления при использовании чисел с плавающей запятой.

C++ — поиск n-значных квадратов

// 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 — поиск n-значных квадратов

# 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)

JavaScript — поиск n-значных квадратов

// 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) + "\n");

    document.write("Largest " + n + "-digit perfect square: " + Math.pow(Math.ceil(Math.sqrt(Math.pow(10, n))) - 1, 2) + "\n");
}

var n1 = 1;
document.write("Number of digits: " + n1 + "\n");
findPerfectSquares(n1);

var n2 = 2;
document.write("Number of digits: " + n2 + "\n");
findPerfectSquares(n2);

var n3 = 3;
document.write("Number of digits: " + n3 + "\n");
findPerfectSquares(n3);

var n4 = 4;
document.write("Number of digits: " + n4 + "\n");
findPerfectSquares(n4);

Кубы: наименьшие и наибольшие n-значные числа

Условие задачи

Дано целое n. Нужно найти наименьшее и наибольшее n-значное число, которое является точным кубом (k^3 для целого k).

Примеры:

• n = 2: наименьший 2-значный куб — 27, наибольший — 64.
• n = 3: наименьший 3-значный куб — 125, наибольший — 729.

Подход

Аналогично квадратам используем корень третьей степени (cbrt):

• наименьший n-значный куб = pow(ceil(cbrt(pow(10, n - 1))), 3)
• наибольший n-значный куб = pow(ceil(cbrt(pow(10, n))) - 1, 3)

Опять же k = ceil(cbrt(10^(n-1))) даёт наименьший куб.

C++ — поиск n-значных кубов

// 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 — поиск n-значных кубов

# 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)

JavaScript — поиск n-значных кубов

// 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) + "\n");

    document.write("Largest " + n + "-digit perfect cube: " + Math.pow(Math.ceil(Math.cbrt(Math.pow(10, (n)))) - 1, 3) + "\n");
}

var n1 = 1;
document.write("Number of digits: " + n1 + "\n");
findPerfectCubes(n1);

var n2 = 2;
document.write("Number of digits: " + n2 + "\n");
findPerfectCubes(n2);

var n3 = 3;
document.write("Number of digits: " + n3 + "\n");
findPerfectCubes(n3);

var n4 = 4;
document.write("Number of digits: " + n4 + "\n");
findPerfectCubes(n4);

Когда подходы дают сбой и альтернативы

Важно: формулы, основанные на sqrt/cbrt и функции ceil, опираются на арифметику с плавающей запятой. Для очень больших n (например, n > 15–16 в типичных языках с двойной точностью) возможны ошибки округления, приводящие к off-by-one при вычислении k.

Альтернативы и решения:

• Использовать целочисленный поиск квадратного/кубического корня (integer nth root). Это надёжно для больших чисел.
• Применить BigInteger/BigInt (Java, Python int — уже произвольной точности) для возведения в степень и проверки длины строки результата.
• Выполнить бинарный поиск k по диапазону [1, 10^ceil(n/2)] для квадратов или по соответствующему верхнему пределу для кубов. Бинарный поиск даёт O(log M) шагов, где M — верхняя граница k.

Контрпример: использование double sqrt для n=308 может дать неверный k из‑за потери точности, поэтому проверяйте результат через целочисленную проверку (например, проверить, что k^2 >= 10^(n-1) и (k-1)^2 < 10^(n-1)).

Практические рекомендации (эвристики)

• Для n <= 15 можно безопасно использовать стандартные sqrt/cbrt с последующей проверкой результата.
• Для n > 15 используйте произвольную точность (BigInt) или целочисленные корни.
• Всегда проверяйте результирующее число на количество цифр: len(str(x)) == n.

Критерии приёмки и тесты

Минимальный набор тестов для функции findPerfectSquares/ findPerfectCubes:

1. n = 1: ожидание квадратов {1,9}, кубов {1,8}
2. n = 2: квадраты {16,81}, кубы {27,64}
3. n = 3: квадраты {100,961}, кубы {125,729}
4. n = 4: квадраты {1024,9801}, кубы {1000,9261}
5. граничные: n = 0 (некорректный ввод) — функция возвращает ошибку/None
6. большие n (например, n = 20): проверка корректности количества цифр и целочисленного подхода

Критерии приёмки:

• Функция возвращает два целых числа (минимальный и максимальный) либо явную ошибку при некорректном n.
• Возвращаемые числа действительно имеют ровно n цифр.
• Для больших n точность гарантирована тестами с проверкой len(str(x)).

Чек-листы для ролей

Разработчик:

• Проверил ввод n > 0
• Реализовал проверку результата через len(str(x))
• Добавил обработку больших чисел (BigInt/BigInteger) при необходимости

Тестировщик:

• Прогнал все тесты из раздела “Критерии приёмки”
• Проверил поведение при некорректных входных данных
• Проверил производительность для больших n

Маленькая методология и контрольные числа

Шаги для безопасной реализации:

1. Проверить, что n — целое > 0.
2. Вычислить кандидат k через ceil(root(10^(n-1))).
3. Вычислить x = k^nth (k^2 или k^3).
4. При необходимости скорректировать k и снова проверить длину числа.
5. Вернуть минимальный и максимальный результаты.

Факт-бокс (примеры):

• n=1: квадрат [1,9], куб [1,8]
• n=2: квадрат [16,81], куб [27,64]
• n=3: квадрат [100,961], куб [125,729]
• n=4: квадрат [1024,9801], куб [1000,9261]

Краткий глоссарий

• ceil — функция округления вверх до целого.
• sqrt — квадратный корень.
• cbrt — кубический корень.
• BigInt/BigInteger — типы целых произвольной точности.

Важно: всегда проверяйте вычисленный результат на количество цифр и при необходимости используйте целочисленные методы для надёжности.

Резюме:

• Формулы с sqrt/cbrt просты и работают для большинства практических n.
• Для гарантированной точности при больших n используйте целочисленные корни или типы произвольной точности.

Если хотите, могу добавить готовые реализации «integer nth-root» для C++, Python и JavaScript и показать, как избежать ошибок округления.