Интересный вызов, но далеко за пределами моих математических навыков. Итак, вот скотина реализация силы в простом C :P
не имеет математическое доказательство, и поэтому не могу доказать это всегда найти решение, но это работает для ввода. Добавление «фруктового» «клинтона» и «овоща» «mccaine» заставляет его работать немного дольше; добавление «абрикоса» сигнализирует о столкновении! (Что сообщается, но не говорит где. Обратите внимание, что столкновение внутри аналогично предметов - фрукты или овощей - на самом деле должно быть разрешено. Я не написал для этого код, но он должен быть относительно простым.)
Чтобы увидеть более длинную последовательность, добавьте «банан». По какой-то причине это должно подняться до 163,13,2. Забавно, добавив «кумкват» (у меня иссякнут фрукты) не займет много времени, и даже с другим «кокосом» это займет не так много времени.
Примечания по реализации:
Вы можете ограничить поиск максимального входного кода 2-байтовое, так как функция mod никогда ничего с большими числами делать. Для согласованности этот код C начинается с тестирования всех значений 1-mod (хотя я не нашел ничего полезного). Затем он проверяет значения 2-мода и, наконец, 3-модовые значения. Если он не найдет значения, вы можете расширить его, чтобы искать длинные последовательности с 4 модами и 5 модами, но время поиска будет увеличиваться логарифмически (!).
Должна быть возможность классифицировать более двух значений; что требует очень незначительной перезаписи кода. Я подозреваю, что поиск матча для всех займет гораздо больше времени.
Также должно быть возможно вернуть другие «индексы», чем 0 и 1; как я пишу это, остальная часть процессора работает на 2 и 0. Однако, похоже, это займет совсем немного времени.
реализация C, перебор:
#include <stdio.h>
#include <stdlib.h>
int main (void)
{
char *fruits[] = { "apple", "pear", "orange"} ; //, "clinton" };
char *veggies[] = { "lettuce", "carrot", "asparagus" }; // , "mccaine" };
int num_f, num_v, found_match;
unsigned short *code[2], max_code = 0;
int i,j, mod_value1, mod_value2, mod_value3;
num_f = sizeof(fruits)/sizeof(fruits[0]);
num_v = sizeof(veggies)/sizeof(veggies[0]);
code[0] = malloc((num_f+num_v)*sizeof(short));
code[1] = malloc((num_f+num_v)*sizeof(short));
for (i=0; i<num_f; i++)
{
code[0][i] = (fruits[i][0]<<8)+fruits[i][1];
code[1][i] = 1;
if (code[0][i] > max_code)
max_code = code[0][i];
}
for (i=0; i<num_v; i++)
{
code[0][num_f+i] = (veggies[i][0]<<8)+veggies[i][1];
code[1][num_f+i] = 0;
if (code[0][num_f+i] > max_code)
max_code = code[0][num_f+i];
}
for (i=0; i<num_f+num_v; i++)
{
for (j=i+1; j<num_f+num_v; j++)
{
if (code[0][i] == code[0][j])
{
printf ("clash!\n");
exit(-1);
}
}
}
printf ("calculating...\n");
for (mod_value1=1; mod_value1<max_code; mod_value1++)
{
found_match = 1;
for (i=0; i<num_f+num_v; i++)
{
if (code[0][i] % mod_value1 != code[1][i])
{
found_match = 0;
break;
}
}
if (found_match)
{
printf ("mod %d should work\n", mod_value1);
break;
}
}
if (found_match)
{
for (i=0; i<num_f; i++)
{
printf ("%s -> %d\n", fruits[i], code[0][i] % mod_value2 % mod_value1);
}
for (i=0; i<num_v; i++)
{
printf ("%s -> %d\n", veggies[i], code[0][num_f+i] % mod_value2 % mod_value1);
}
} else
{
for (mod_value1=1; mod_value1<max_code; mod_value1++)
{
for (mod_value2=mod_value1+1; mod_value2<max_code; mod_value2++)
{
found_match = 1;
for (i=0; i<num_f+num_v; i++)
{
if (code[0][i] % mod_value2 % mod_value1 != code[1][i])
{
found_match = 0;
break;
}
}
if (found_match)
{
printf ("mod %d mod %d should work\n", mod_value2, mod_value1);
break;
}
}
if (found_match)
break;
}
if (found_match)
{
for (i=0; i<num_f; i++)
{
printf ("%s -> %d\n", fruits[i], code[0][i] % mod_value2 % mod_value1);
}
for (i=0; i<num_v; i++)
{
printf ("%s -> %d\n", veggies[i], code[0][num_f+i] % mod_value2 % mod_value1);
}
} else
{
for (mod_value1=1; mod_value1<max_code; mod_value1++)
{
for (mod_value2=mod_value1+1; mod_value2<max_code; mod_value2++)
{
for (mod_value3=mod_value2+1; mod_value3<max_code; mod_value3++)
{
found_match = 1;
for (i=0; i<num_f+num_v; i++)
{
if (code[0][i] % mod_value3 % mod_value2 % mod_value1 != code[1][i])
{
found_match = 0;
break;
}
}
if (found_match)
{
printf ("mod %d mod %d mod %d should work\n", mod_value3, mod_value2, mod_value1);
break;
}
}
if (found_match)
break;
}
if (found_match)
break;
}
if (found_match)
{
for (i=0; i<num_f; i++)
{
printf ("%s -> %d\n", fruits[i], code[0][i] % mod_value3 % mod_value2 % mod_value1);
}
for (i=0; i<num_v; i++)
{
printf ("%s -> %d\n", veggies[i], code[0][num_f+i] % mod_value3 % mod_value2 % mod_value1);
}
}
}
}
return 0;
}
Результат для оригинального 3 фрукта, список 3 вегетарианец:
mod 25 mod 2 should work
apple -> 1
pear -> 1
orange -> 1
lettuce -> 0
carrot -> 0
asparagus -> 0
Late Результат, для полезного выхода 2 и 0:
mod 507 mod 8 mod 3 should work
apple -> 2
pear -> 2
orange -> 2
lettuce -> 0
carrot -> 0
asparagus -> 0
Позже результат с «спорным» «томатом» добавлен как a Категория 2:
mod 103 mod 7 mod 3 should work
apple -> 1
pear -> 1
orange -> 1
lettuce -> 0
carrot -> 0
asparagus -> 0
tomato -> 2
Похоже, вы поняли, что это грубая сила. Я не думаю, что есть какой-то особый умный способ обойти это, вы сомневаетесь, это просто сложный способ спросить, есть ли проблема с остановкой решения. – iluvcapra
Я только что нашел этот вопрос http://programmers.stackexchange.com/questions/249458/given-known-inputs-and-outputs-can-we-generate-candidate-functions-that-will-ma – user3109679
Что это такое делать с базами данных, или C в этом отношении? –