Друг ходил на собеседование по Oracle. Задали такую логическую задачу.

Есть 8 шаров, причем один из них с дефектом (легче, тяжелее — неизвестно). Нужно за 3 взвешивания выявить его.

Он решил за 4 взвешивания.

Кто знает, как это сделать за 3?

V>Есть 8 шаров, причем один из них с дефектом (легче, тяжелее — неизвестно). Нужно за 3 взвешивания выявить его.

V>Он решил за 4 взвешивания.

V>Кто знает, как это сделать за 3?

Задачка очень известная. Делишь шары на 3,3 и 2. Взвешиваешь 3 и 3... А дальше возможны варианты ...

4->2->1

Здравствуйте, Crackjack, Вы писали:

4->>2->1

ну и? четыре на четыре взвесил, что-то будет тяжелее, что-то легче. В условиях ведь ясно сказано — неизвестно какой дефект.

Эталон нужен

Здравствуйте, Crackjack, Вы писали:

4->>2->1

Я тоже так решил, но если не известно дефектный шар меньше или больше как в конце решить какой из двух дефектный?

Здравствуйте, vralch, Вы писали:

V>Друг ходил на собеседование по Oracle. Задали такую логическую задачу.

V>Есть 8 шаров, причем один из них с дефектом (легче, тяжелее — неизвестно). Нужно за 3 взвешивания выявить его.

V>Он решил за 4 взвешивания.

V>Кто знает, как это сделать за 3?

Если известен нормальный вес, то:
Делим 8 шаров на 2 группы. Берем первую группу и взвешиваем. Если есть отклонения, то берем из этой четверки еще два шара, если нет из второй. Взвешиваем их. Если дефект не найден, то остается взвесить только один шар. (их осталось два)
Пример:

* * * * * * * +, где * — нормальный шарик, + — с дефектом

1я 4ка * * * *
Берем из второй группы первую пару * *
Берем из второй группы второй партии любой — либо * либо +
Итого 3 взвешивания.

Здравствуйте, Nikto, Вы писали:

N>Задачка очень известная. Делишь шары на 3,3 и 2. Взвешиваешь 3 и 3... А дальше возможны варианты ...

Чота поторопился. Сорри . Надо выбрать 4 шара, разбить их на пары, взесить меду собой:
1.) если равны (значит они стали эталоном), то берем любые 3 шара из оставшихся 4-х и 3 шара из этих 4-х.
Взвешиваем:
а.) равны — все понятно
б.) меньше/больше, все понятно

2.) если не равны, то все тоже самое .

Здравствуйте, Nikto, Вы писали:

V>>Есть 8 шаров, причем один из них с дефектом (легче, тяжелее — неизвестно). Нужно за 3 взвешивания выявить его.

V>>Он решил за 4 взвешивания.

V>>Кто знает, как это сделать за 3?

N>Задачка очень известная. Делишь шары на 3,3 и 2. Взвешиваешь 3 и 3... А дальше возможны варианты ...

1) делим на 2 кучки по 4. А и Б.
А делим на 2 и 2, взвешиваем.
в результате знаем 4 заведомо хороших шара.
2) берем 4 плохих шара делим на 2 кучки А' и Б'
делим А' попалам. взвешиваем.
находим 2 заведомо хороших шара.
3) Осталось выяснить кокой из 2х шаров плохой.
берем один из них и взвешиваем с хорошим.

Здравствуйте, ghost92, Вы писали:

G>1) делим на 2 кучки по 4. А и Б.
G> А делим на 2 и 2, взвешиваем.
G> в результате знаем 4 заведомо хороших шара.
G>2) берем 4 плохих шара делим на 2 кучки А' и Б'
G> делим А' попалам. взвешиваем.
G> находим 2 заведомо хороших шара.
G>3) Осталось выяснить кокой из 2х шаров плохой.
G> берем один из них и взвешиваем с хорошим.

Я раньше решение запостил .

Здравствуйте, Nechaev, Вы писали:

N>Здравствуйте, Crackjack, Вы писали:

4->>>2->1

N>Я тоже так решил, но если не известно дефектный шар меньше или больше как в конце решить какой из двух дефектный?

Пытался написать алгоритм, не получилось: слишком геморно. Смысл примерно в следующем: взвешиваем две ПАРЫ шаров: вес одинаковый, значит битый шар в других 4-х. разный: берем любую из пар и взвешиваем. вес разный: берем из полученной пары шарик и сравниваем с шариком из другой пары: вес разный — это он, вес одинаковый — другой.
Случай, если при первом взвешивании пары оказались одинаовыми: берем пару из уже взвешенных и взвешиваем с парой из не взвешенных. Вес одинаковый: взвешиваем любой из оставшихся шариков. Разный — любой из полученных шариков с эталонным (из первой четверки).

Здравствуйте, vralch, Вы писали:

V>Друг ходил на собеседование по Oracle. Задали такую логическую задачу.

V>Есть 8 шаров, причем один из них с дефектом (легче, тяжелее — неизвестно). Нужно за 3 взвешивания выявить его.

V>Он решил за 4 взвешивания.

V>Кто знает, как это сделать за 3?

Для Oracle :

SQL> create table balls (b1 number,
  2  
SQL> ed
Записано файл afiedt.buf

  1  create table balls (
  2  b1 number,
  3  b2 number,
  4  b3 number,
  5  b4 number,
  6  b5 number,
  7  b6 number,
  8  b7 number,
  9  b8 number);

Таблица создана.

SQL> create or replace procedure set_balls
  2  as
  3  str varchar2(2000);
  4  n number;
  5  begin
  6  update balls
  7  set
  8  b1 = 1,
  9  b2 = 1,
 10  b3 = 1,
 11  b4 = 1,
 12  b5 = 1,
 13  b6 = 1,
 14  b7 = 1,
 15  b8 = 1;
 16  n := round(dbms_random.value, 1);
 17  --dbms_output.put_line('n='||n);
 18  str := 'update balls set b'||round(dbms_random.value(1,8))||' = '||
 19  to_char(n, 'fm0.0');
 20  --dbms_output.put_line('str='||str);
 21  execute immediate str;
 22* end;
SQL> /

Процедура создана.

SQL> exec set_balls;

Процедура PL/SQL успешно завершена.

SQL> select
  2  case when (b1+b2 = b3+b4)
  3     then    (case when (b1+b2=b5+b6)
  4             then (case when (b1=b7) then 8
  5             else 7
  6             end)
  7     else    (case when (b1=b5) then 6
  8             else 5
  9             end)
 10     end)
 11  else
 12     (case when (b1=b2)
 13             then (case when (b1=b3) then 4
 14             else 3
 15             end)
 16     else
 17             (case when (b1=b3) then 2
 18             else 1
 19             end)
 20     end)
 21  end invalid_ball
 22  from balls;

INVALID_BALL
------------
           5

SQL> select * from balls;

       B1        B2        B3        B4        B5        B6        B7        B8
--------- --------- --------- --------- --------- --------- --------- ---------
        1         1         1         1        ,8         1         1         1

SQL>

Здравствуйте, vralch, Вы писали:

V>Друг ходил на собеседование по Oracle. Задали такую логическую задачу.

V>Есть 8 шаров, причем один из них с дефектом (легче, тяжелее — неизвестно). Нужно за 3 взвешивания выявить его.

V>Он решил за 4 взвешивания.

V>Кто знает, как это сделать за 3?

вообще говоря 8 шаров как-то даже скучно.
вот 10 уже веселее.
А из какого максимального кол-ва шаров можно определить 1 с дефектом за 3 взвешивания?

Здравствуйте, vralch, Вы писали:

V>Друг ходил на собеседование по Oracle. Задали такую логическую задачу.

V>Есть 8 шаров, причем один из них с дефектом (легче, тяжелее — неизвестно). Нужно за 3 взвешивания выявить его.

V>Он решил за 4 взвешивания.

V>Кто знает, как это сделать за 3?


Правильный алгоритм решения следующий:

1. На обе чашки весов ложим по 3 шара. Если их вес совпадает, значит шара с дефектом в этих шести нет, он остался в тех двух.

Если дефектный в одном из 2х оставшихся (7 или 8), то взвешиваем например 7 с одним из этих 6ти.
1.1. Если вес равный, значит "глючный" шар №8. В этом случае мы точно не знаем характер глюка.
1.2. Если не равный, то глючный — тот что взяли,т.е. №7 . В этом будем знать характер глюка.

2. Если вес не совпадает, то получаем 2 группы по 3 шара. Пусть это будет 1,2,3 и 4,5,6. Также мы знаем что 7 и 8 являются эталонами нормального веса.
Итак второе взвешивание — 1,2,3,6 против 4,5,7,8. (Пусть при первом взвешивании 1,2,3 оказали легче).
2.1. 1,2,3,6 оказываются тяжелее чем 4,5,7,8. Т.е. мы получили перевес за счет шара №6. Вывод — №6 является глючным, причем тяжелее эталона.
2.2. 1,2,3,6 оказываются легче чем 4,5,7,8. Т.е. глючный шар или 4 или 5 (Поскольку мы уже знаем что 7 и 8 являются эталонами).
3. Берем например 4 и 7.
3.1 4ка меньше чем 7 — значит глюкавый шар №4, причем глюк — недовес
3.2 4Ка больше чем 7 — значит глюкавый шар №4, причем глюк — перевес
3.3. 4Ка равна по весу 7 — значит глюкавый шар №5, характер глюка остается неизвестен

Вот моё решение максимум за 3 хода. Максимум — потому как в процессе взвешивания может оказаться что и 3х взвешиваний не надо.

Здравствуйте, vralch, Вы писали:

V>Друг ходил на собеседование по Oracle. Задали такую логическую задачу.

Интересное собеседование. Когда-то давно (год эдак 85-ый) в школе мы проходили последовательности и наш математик нам задал задачку — вычислить следующий элемент последовательности. А последовательность была такая:

7, 10, 13, 18, 21, 23, 28, X

Найдите X

Вот это я понимаю, задачка. На знание "предметной области"

Здравствуйте, ghost92, Вы писали:

G>Здравствуйте, vralch, Вы писали:

V>>Друг ходил на собеседование по Oracle. Задали такую логическую задачу.

V>>Есть 8 шаров, причем один из них с дефектом (легче, тяжелее — неизвестно). Нужно за 3 взвешивания выявить его.

V>>Он решил за 4 взвешивания.

V>>Кто знает, как это сделать за 3?

G>вообще говоря 8 шаров как-то даже скучно.
G>вот 10 уже веселее.
G>А из какого максимального кол-ва шаров можно определить 1 с дефектом за 3 взвешивания?

12 - точно. Сам решал. Ещё в щколе.
И можно определить легче или тяжелей.

Здесь по-моему было и 13.
Не вдавался......









.

Здравствуйте, ghost92, Вы писали:

G>А из какого максимального кол-ва шаров можно определить 1 с дефектом за 3 взвешивания?

13, если не нужно знать, легче он или тяжелее. Иначе — 12.

V>Есть 8 шаров, причем один из них с дефектом (легче, тяжелее — неизвестно). Нужно за 3 взвешивания выявить его.

V>Он решил за 4 взвешивания.

V>Кто знает, как это сделать за 3?

решил?
а теперь то же самое, только не 8, а 12 шаров. тоже решается

Здравствуйте, vralch, Вы писали:

V>Друг ходил на собеседование по Oracle. Задали такую логическую задачу.

В Российский Oracle? Если не секрет, на какую позицию?

Здравствуйте, Spidola, Вы писали:

S>Здравствуйте, vralch, Вы писали:

V>>Друг ходил на собеседование по Oracle. Задали такую логическую задачу.

S>Интересное собеседование. Когда-то давно (год эдак 85-ый) в школе мы проходили последовательности и наш математик нам задал задачку — вычислить следующий элемент последовательности. А последовательность была такая:

S>7, 10, 13, 18, 21, 23, 28, X

S>Найдите X
.... 31 34 37 38 42 45 .......
или
.... 33 36 39 41 40 ......

S>Вот это я понимаю, задачка. На знание "предметной области"

Ну, если действительно понимаешь, то выбирай.
Если что могу ещё










.

S>>7, 10, 13, 18, 21, 23, 28, X

31, 32, 37, 40