Агент007
index.htm - английский текст,
agent007.zip - все программы,
Рассмотрим школьную задачу, которая лет десять назад была опубликована в журнале "Квант" на страничке для младших школьников. Какое там приводилось решение - не помню, но я эту задачу использую на занятиях со студентами 2 курса, когда по алгебре проходим тему "подстановки". На этой задаче демонстрируются все основные алгебраические понятия.
Задача прекрасная, так как будем решать ее с помощью суперкомпилятора. Задачи подобного типа я отношу к "рекурсивным" задачам - условие закручено само на себя.
Задача.
Шеф разведки, где служит Агент007, в целях полной конспирации и надежности придумал схему взаимной слежки своих агентов.
Агент001 следит за тем агентом, который следит за Агентом002.
Агент002 следит за тем агентом, который следит за Агентом003.
Агент003 следит за тем агентом, который следит за Агентом004.
Агент004 следит за тем агентом, который следит за Агентом005.
Агент005 следит за тем агентом, который следит за Агентом006.
Агент006 следит за тем агентом, который следит за Агентом007.
Агент007 следит за тем агентом, который следит за Агентом001.
Все шло нормально, пока на службу не пришел Агент008. Никак у шефа не получается составить подобную схему взаимной слежки для восьми агентов.
Задача 1. Какая схема взаимной слежки была сначала (за кем следит каждый агент)?
Задача 2. Почему при 8 агентах у шефа ничего не получается ?
Решение с помощью суперкомпилятора.
Исходная Ява-программа:
class Agent007 {
public static final int nofAgents = 7;
static class State {
int[] agents = new int[nofAgents];
State (int[] agents) {
for (int i=0; i<nofAgents; i++) {
this.agents[i] = agents[i];
}
}
}
public static void main (String args[]) throws Exception {
int[] agents = { 4, 5, 6, 0, 1, 2, 3};
checkAndPrint (agents);
}
public static void checkAndPrint(int[] agents1) throws Exception {
int[] agents = new int[nofAgents];
for (int i=0; i<nofAgents; i++) {
agents[i] = agents1[i];
}
State s = new State (agents);
for (int i=0; i<nofAgents; i++) {
if ( iAgent(s, iAgent(s, i)) != next(i)) throw new Exception();
}
for (int i=0; i<nofAgents; i++) {
System.out.println( "The agent 00" + (i+1) +
" watches the agent 00" +
(s.agents[i] +1) );
}
}
public static int iAgent(State s, int ia) throws Exception {
for (int i=0; i<nofAgents; i++) {
if (s.agents[ia]==i) {s.agents[ia]=i; return i;}
}
throw new Exception();
}
public static int next(int iAgent) {
if(iAgent==nofAgents-1) return 0;
else return iAgent+1;
}
}
|
Для 8 агентов единственное изменение в операторе nofAgents = 7;
Результат суперкомпиляции для 7 агентов:
public static void checkAndPrint (final int[] agents1_1)
throws java.lang.Exception
{
final int[] agents_2 = new int[7];
final int agents1_0_3 = agents1_1[0];
agents_2[0] = agents1_0_3;
final int agents1_1_6 = agents1_1[1];
agents_2[1] = agents1_1_6;
final int agents1_2_9 = agents1_1[2];
agents_2[2] = agents1_2_9;
final int agents1_3_12 = agents1_1[3];
agents_2[3] = agents1_3_12;
final int agents1_4_15 = agents1_1[4];
agents_2[4] = agents1_4_15;
final int agents1_5_18 = agents1_1[5];
agents_2[5] = agents1_5_18;
final int agents1_6_21 = agents1_1[6];
agents_2[6] = agents1_6_21;
final int[] agents_34 = new int[7];
agents_34[0] = agents1_0_3;
agents_34[1] = agents1_1_6;
agents_34[2] = agents1_2_9;
agents_34[3] = agents1_3_12;
agents_34[4] = agents1_4_15;
agents_34[5] = agents1_5_18;
agents_34[6] = agents1_6_21;
if (agents1_0_3 == 0
|| agents1_0_3 == 1
|| agents1_0_3 == 2
|| agents1_0_3 == 3
|| agents1_0_3 != 4
|| agents1_4_15 == 0
|| agents1_4_15 != 1
|| agents1_1_6 == 0
|| agents1_1_6 == 1
|| agents1_1_6 == 2
|| agents1_1_6 == 3
|| agents1_1_6 == 4
|| agents1_1_6 != 5
|| agents1_5_18 == 0
|| agents1_5_18 == 1
|| agents1_5_18 != 2
|| agents1_2_9 == 0
|| agents1_2_9 == 1
|| agents1_2_9 == 2
|| agents1_2_9 == 3
|| agents1_2_9 == 4
|| agents1_2_9 == 5
|| agents1_2_9 != 6
|| agents1_6_21 == 0
|| agents1_6_21 == 1
|| agents1_6_21 == 2
|| agents1_6_21 != 3
|| agents1_3_12 != 0) {
throw new java.lang.Exception();}
java.lang.System.out.println("The agent 001 watches the agent 005") /*virtual*/;
java.lang.System.out.println("The agent 002 watches the agent 006") /*virtual*/;
java.lang.System.out.println("The agent 003 watches the agent 007") /*virtual*/;
java.lang.System.out.println("The agent 004 watches the agent 001") /*virtual*/;
java.lang.System.out.println("The agent 005 watches the agent 002") /*virtual*/;
java.lang.System.out.println("The agent 006 watches the agent 003") /*virtual*/;
java.lang.System.out.println("The agent 007 watches the agent 004") /*virtual*/;
return;
}
//----------------------------- 11 sec - JScp version 0.1.22
|
Теперь записываем ответ
Агент001 следит за Агентом005,
Агент002 следит за Агентом006,
Агент003 следит за Агентом007,
Агент004 следит за Агентом001,
Агент005 следит за Агентом002,
Агент006 следит за Агентом003,
Агент007 следит за Агентом004.
Для 8 агентов результат суперкомпиляции такой:
public static void checkAndPrint (final int[] agents1_1)
throws java.lang.Exception
{
final int[] agents_2 = new int[8];
final int agents1_0_3 = agents1_1[0];
agents_2[0] = agents1_0_3;
final int agents1_1_6 = agents1_1[1];
agents_2[1] = agents1_1_6;
final int agents1_2_9 = agents1_1[2];
agents_2[2] = agents1_2_9;
final int agents1_3_12 = agents1_1[3];
agents_2[3] = agents1_3_12;
final int agents1_4_15 = agents1_1[4];
agents_2[4] = agents1_4_15;
final int agents1_5_18 = agents1_1[5];
agents_2[5] = agents1_5_18;
final int agents1_6_21 = agents1_1[6];
agents_2[6] = agents1_6_21;
final int agents1_7_24 = agents1_1[7];
agents_2[7] = agents1_7_24;
final int[] agents_38 = new int[8];
agents_38[0] = agents1_0_3;
agents_38[1] = agents1_1_6;
agents_38[2] = agents1_2_9;
agents_38[3] = agents1_3_12;
agents_38[4] = agents1_4_15;
agents_38[5] = agents1_5_18;
agents_38[6] = agents1_6_21;
agents_38[7] = agents1_7_24;
throw new java.lang.Exception();
}
//-------------------------------------- 39 sec - JScp version 0.1.22
|
Ответ: задача решений не имеет.
Не имеет смысла пускать на счет исходную программу для 8 агентов - она всегда будет выдавать
Exception in thread "main" java.lang.Exception
В строчках
for (int i=0; i<nofAgents; i++)
{
if (
iAgent(s, iAgent(s, i)) != next(i)) throw new Exception();
}
происходит умножение подстановки на себя и сравнение результата умножения с подстановкой из одного цикла (0 1 2 3 4 5 6)
Подчеркну, что я здесь ничего не программирую, записываю условие задачи - и только. Полученное никак не годится для каких-либо осмысленных пусков на счет при обычном, без использования суперкомпилятора, программировании.
Действительно, сейчас имеется предикат, принимающий значение истина на ответе к задаче, и ложь - на не ответе. Если я знаю ответ, то могу пустить программу на счет и получу на экране истину, если не знаю ответа, то тоже могу пустить программу на счет и получить на экране, скорее всего, ложь.
С использованием суперкомпилятора все осмысленно.
Алгебраическое решение.
Запишем искомую схему взаимной слежки в виде подстановки а на 8 символах. По условию задачи a^2 = ( 1 2 3 4 5 6 7 8 ) - запись подстановки в виде одного цикла.
Квадрат любой подстановки является четной подстановкой, но подстановка, которая получилась - ( 1 2 3 4 5 6 7 8 ) - нечетная. Противоречие показывает невозможность решения второй задачи.
В случае первой задачи имеем a^2 = ( 1 2 3 4 5 6 7 ) = b.
Подстановка b обладает свойством b^7 = e - тождественная подстановка, значит,
b^8 = b, при этом b = a^2, поэтому можно взять a = b^4 = ( 1 5 2 6 3 7 4 ).
Ответ :
Агент001 следит за Агентом005,
Агент002 следит за Агентом006,
Агент003 следит за Агентом007,
Агент004 следит за Агентом001,
Агент005 следит за Агентом002,
Агент006 следит за Агентом003,
Агент007 следит за Агентом004.