Dnia Mon, 09 Jul 2012 16:34:16 +0200, slawek napisal:

> Gdy myślałem o jakichś /łatwych/ problemikach, żeby nie zapętlać się na
> hetmanach itp. "standardach"... coś takiego przyszło mi do głowy:
>
> Mamy N cylindrycznych bolców (trzpieni?), które powinny pasować do N
> otworów, każdy otwór jest wywiercony w jednej z N sześciennych kostek.
> Bolce nie pasują jednak dokładnie i trzeba dobrać możliwie najlepiej
> pary (bolec,kostka). Ok, algorytm jest trywialny - posortować średnice
> bolców, posortować średnice otworów, ... nuda.
>
> Ale teraz wprowadzamy małą modyfikację - otworów jest 3N, tzn. w każdej
> kostce są trzy. Nadal jednak trzeba znaleźć najlepsze pary (bolec,
> kostka), choć tym razem 2 otwory w kostce będą nieużyte. (Można sobie
> wyobrazić, że otwory w kostce są nawiercone wzdłuż osi x,y,z, a bolec
> np. mocuje kostkę do ściany.)
>
> Uwaga: w obu przypadkach możliwe jest że będą bolce nie pasujące do
> jakiejkolwiek kostki (jeżeli różnica pomiędzy średnicą otworu i średnicą
> bolca nie spełnia warunku b > (D-d) > a ).
>
> Nie potrzebuję rozwiązania tego zadania (choć jeżeli ktoś chce?), lecz
> raczej czy to zadanie jest - według was - łatwe, czy też dość trudne?
>
> (Nota bene, swego czasu przebojem był program parujący tranzystory
> komplementarne na podstawie ich charakterystyk połączony przez kartę
> AD/DA do PC. Ale to problem "z jedną dziurką".)

Zacznij od tych niepasujących bolców, trywialna eliminacja od góry. Potem
z górki, a właściwie z dołu.

Edek