Рекурсивные числа
index.htm - английский текст,
recnumb.zip - все программы,
Задача. Найдите такое 10-значное число, в котором первая слева цифра равняется количеству нулей в этом числе, вторая цифра равняется количеству единиц в этом числе, и так далее, десятая цифра равняется количеству девяток в этом числе.
Например, подходит число 6 210 001 000 . Действительно, в нем 6 нулей, 2 единицы, 1 двойка, 1 шестерка, и других цифр нет.
Задача обобщается для чисел произвольной разрядности.
Задача несколько раз мне встречалась в сборниках олимпиадных задач для 10-значного числа, при этом каждый раз приводился только ответ без решения.
Ответ в этой задаче достаточно любопытен.
Для 2-значных чисел - решений нет,
Для 3-значных чисел - решений нет,
Для 4-значных чисел - два решения - 1210 и 2020,
Для 5-значных чисел - одно решение - 21200,
Для 6-значных чисел - решений нет,
Для 7-значных чисел - одно решение - 3211000,
Для n-значных чисел, n>7 - одно решение -
n-4 , 2 , 1 , 0 , ... , 0 , 1 , 0 , 0 , 0 .
Решаем задачу при помощи суперкомпилятора.
Исходная программа на Яве:
class RecNumb {
public static final int nofDigits = 5;
static class State {
int[] digits = new int[nofDigits];
State (int[] digits) {
for (int i=0; i<nofDigits; i++) {
this.digits[i] = digits[i];
}
}
}
public static void main (String args[]) throws Exception {
int[] digits = { 2, 1, 2, 0, 0};
checkAndPrint (digits);
}
public static void checkAndPrint(int[] digits1) throws Exception {
int[] digits = new int[nofDigits];
for (int i=0; i<nofDigits; i++) {
digits[i] = digits1[i];
}
State s = new State (digits);
for (int i=0; i<nofDigits; i++) {
int sum = iDigit(s, i);
for (int j=0; j<nofDigits; j++) {
if(iDigit(s, j)==i) sum--;
if(sum<0) throw new Exception();
}
if(sum>0) throw new Exception();
}
String out = "";
for (int i=0; i<nofDigits; i++) out = out + s.digits[i];
System.out.println(out);
}
public static int iDigit(State s, int ia) throws Exception {
for (int i=0; i<nofDigits; i++) {
if (s.digits[ia]==i) {s.digits[ia]=i; return i;}
}
throw new Exception();
}
|
nofDigits - задает разрядность чисел в примере.
Массив int[] digits служит для контрольного пуска на счет. В тех случаях, когда ответа нет, пуск бессмысленен.
В архивированном приложении - все примеры (они занумерованы по номерам примеров), здесь приведу остаточные программы - они маленькие.
nofDigits = 2 (решений нет)
public static void checkAndPrint (final int[] digits1_1)
throws java.lang.Exception
{
final int[] digits_2 = new int[2];
final int digits1_0_3 = digits1_1[0];
digits_2[0] = digits1_0_3;
final int digits1_1_6 = digits1_1[1];
digits_2[1] = digits1_1_6;
final int[] digits_14 = new int[2];
digits_14[0] = digits1_0_3;
digits_14[1] = digits1_1_6;
throw new java.lang.Exception();
}
//--------------------------- 0 sec - JScp version 0.1.22
|
nofDigits = 3 (решений нет)
public static void checkAndPrint (final int[] digits1_1)
throws java.lang.Exception
{
final int[] digits_2 = new int[3];
final int digits1_0_3 = digits1_1[0];
digits_2[0] = digits1_0_3;
final int digits1_1_6 = digits1_1[1];
digits_2[1] = digits1_1_6;
final int digits1_2_9 = digits1_1[2];
digits_2[2] = digits1_2_9;
final int[] digits_18 = new int[3];
digits_18[0] = digits1_0_3;
digits_18[1] = digits1_1_6;
digits_18[2] = digits1_2_9;
throw new java.lang.Exception();
}
//--------------------- 1 sec - JScp version 0.1.22
|
nofDigits = 4 (два решения)
public static void checkAndPrint (final int[] digits1_1)
throws java.lang.Exception
{
final int[] digits_2 = new int[4];
final int digits1_0_3 = digits1_1[0];
digits_2[0] = digits1_0_3;
final int digits1_1_6 = digits1_1[1];
digits_2[1] = digits1_1_6;
final int digits1_2_9 = digits1_1[2];
digits_2[2] = digits1_2_9;
final int digits1_3_12 = digits1_1[3];
digits_2[3] = digits1_3_12;
final int[] digits_22 = new int[4];
digits_22[0] = digits1_0_3;
digits_22[1] = digits1_1_6;
digits_22[2] = digits1_2_9;
digits_22[3] = digits1_3_12;
if (digits1_0_3 == 0) {
throw new java.lang.Exception();}
if (digits1_0_3 == 1) {
if (digits1_1_6 == 0
|| digits1_1_6 == 1
|| digits1_1_6 != 2
|| digits1_2_9 == 0
|| digits1_2_9 != 1
|| digits1_3_12 != 0) {
throw new java.lang.Exception();}
java.lang.System.out.println("1210") /*virtual*/;}
else {
if (digits1_0_3 != 2
|| digits1_1_6 != 0
|| digits1_2_9 == 0
|| digits1_2_9 == 1
|| digits1_2_9 != 2
|| digits1_3_12 != 0) {
throw new java.lang.Exception();}
java.lang.System.out.println("2020") /*virtual*/;}
return;
}
//-------------------------------- 6 sec - JScp version 0.1.22
|
nofDigits = 5 (одно решение)
public static void checkAndPrint (final int[] digits1_1)
throws java.lang.Exception
{
final int[] digits_2 = new int[5];
final int digits1_0_3 = digits1_1[0];
digits_2[0] = digits1_0_3;
final int digits1_1_6 = digits1_1[1];
digits_2[1] = digits1_1_6;
final int digits1_2_9 = digits1_1[2];
digits_2[2] = digits1_2_9;
final int digits1_3_12 = digits1_1[3];
digits_2[3] = digits1_3_12;
final int digits1_4_15 = digits1_1[4];
digits_2[4] = digits1_4_15;
final int[] digits_26 = new int[5];
digits_26[0] = digits1_0_3;
digits_26[1] = digits1_1_6;
digits_26[2] = digits1_2_9;
digits_26[3] = digits1_3_12;
digits_26[4] = digits1_4_15;
if (digits1_0_3 == 0
|| digits1_0_3 == 1
|| digits1_0_3 != 2
|| digits1_1_6 == 0
|| digits1_1_6 != 1
|| digits1_2_9 == 0
|| digits1_2_9 == 1
|| digits1_2_9 != 2
|| digits1_3_12 != 0
|| digits1_4_15 != 0) {
throw new java.lang.Exception();}
java.lang.System.out.println("21200") /*virtual*/;
return;
}
//------------------------------- 135 sec - JScp version 0.1.22
|
Время суперкомпиляции резко увеличивается, поэтому на этом эксперименты были прекращены.
Схема математического решения.
Пусть a0 , a1 , ... , an - цифры искомого n+1-значного числа. Подсчет количества цифр (=n+1) различными способами (от перестановки мест слагаемых сумма не меняется) дает два соотношения
a0 + a1 + ... + an = n+1
0*a0 + 1*a1 + 2*a2 + ... + n*an = n+1
Т.е., сумма цифр равняется значности числа, и сумма с коэффициентами тоже равняется значности числа.
Далее идет какой-то перебор возникающих вариантов с учетом большого количества нулей.