|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Serge Kanilo 2:5020/400 04 Oct 2001 23:47:59
To : Roman Kirillov
Subject : Re: Интересная задача
--------------------------------------------------------------------------------
"Roman Kirillov" <Roman.Kirillov@p63.f21.n5057.z2.fidonet.org> wrote in
message news:1197717106@p63.f21.n5057.z2.ftn...
> Пpивет, All!
> Хочу пpедложить тебе сабж - пpосто pазмять мозги. Лично я над ним всю ночь
> думал, и таки пpидумал pешение.
> Итак. Есть 12 монет. Одна - фальшивая, отличается по весу (неизвестно,
> легче или тяжелее). Hеобходимо за 3 взвешвания вычслить сию монету.
Задачка довольно старая, и главная проблема - как просто описать решение.
Hакрапал тут примитивный код
const int HEAVY =3;
const int LIGHT =1;
const int NORMAL =2;
int Coins[12];
int Number(int *A){ return A-Coins; }
int FindFalseCoinFrom2(int*A,int*B,int*C){
if(*A!=*C)
return Number(A);
return Number(B);
}
int FindLightCoinFrom3(int*A){
if(A[0]>A[1])
return Number(A+1);
if(A[0]<A[1])
return Number(A);
return Number(A+2);
}
int FindHeavyCoinFrom3(int*A){
if(A[0]>A[1])
return Number(A);
if(A[0]<A[1])
return Number(A+1);
return Number(A+2);
}
int FindFalseCoinFrom4(int*A){
if(A[0]!=A[1])
return FindFalseCoinFrom2(A,A+1,A+2);
return FindFalseCoinFrom2(A+2,A+3,A);
}
int FindFalseCoinFrom444(int*A,int*B,int*C){
// sum(A)>sum(B), C is NORMAL
if(A[0]+A[1]+A[2]+B[3]>C[0]+C[1]+C[2]+A[3])
return FindHeavyCoinFrom3(A);
if(A[0]+A[1]+A[2]+B[3]<C[0]+C[1]+C[2]+A[3])
return FindFalseCoinFrom2(A+3,B+3,A);
return FindLightCoinFrom3(B);
}
int FindFalseCoinFrom12(int*A){
if(A[0]+A[1]+A[2]+A[3]>A[4]+A[5]+A[6]+A[7])
return FindFalseCoinFrom444(A,A+4,A+8);
if(A[0]+A[1]+A[2]+A[3]<A[4]+A[5]+A[6]+A[7])
return FindFalseCoinFrom444(A+4,A,A+8);
return FindFalseCoinFrom4(A+8);
}
и проверочка всех вариантов
int*A =Coins;
bool goodResult =true;
// для варианта с более тяжелой
for(int falseCoin=0; falseCoin<12; falseCoin++){
for(int aCoin=0; aCoin<12; aCoin++) A[aCoin]=NORMAL;
A[falseCoin]=HEAVY;
int whichCoin =FindFalseCoinFrom12(A);
if(whichCoin!=falseCoin) goodResult =false;
}
// и для варианта с более легкой монетой
for(int falseCoin=0; falseCoin<12; falseCoin++){
for(int aCoin=0; aCoin<12; aCoin++) A[aCoin]=NORMAL;
A[falseCoin]=LIGHT;
int whichCoin =FindFalseCoinFrom12(A);
if(whichCoin!=falseCoin) goodResult =false;
}
здесь проверяем, и видим, что goodResult всегда true,
и значит алгоритм ловит все варианты.
Cheers,
Serge
--- ifmail v.2.15dev5
* Origin: Excite@Home - The Leader in Broadband http://home.com/f (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
