Средний груз
От: nikholas Россия  
Дата: 01.02.17 14:28
Оценка: 15 (3)
Имеется гирьки одинаковые по форме но попарно различные по весу.
За одну операцию можно найти средннюю по весу из 5 гирек.
За какое наименьшее число таких операций можно найти среднюю по весу из 7 гирек?
Re: Средний груз
От: kov_serg Россия  
Дата: 01.02.17 20:16
Оценка:
Здравствуйте, nikholas, Вы писали:

N>Имеется гирьки одинаковые по форме но попарно различные по весу.

N>За одну операцию можно найти средннюю по весу из 5 гирек.
N>За какое наименьшее число таких операций можно найти среднюю по весу из 7 гирек?

3
Re[2]: Средний груз
От: nikholas Россия  
Дата: 02.02.17 11:47
Оценка:
Здравствуйте, kov_serg, Вы писали:

_>3


Не верю!
Re[3]: Средний груз
От: kov_serg Россия  
Дата: 02.02.17 19:50
Оценка:
Здравствуйте, nikholas, Вы писали:

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


_>>3


N>Не верю!


Тогда 7.
F функция которая возвращает медианный груз из 5 грузов,
все грузы попарно разные,
мы можем делать метки на грузах что бы их отличать

Как-то так
1. берём g1=F(первые 5) находим g1
2. берём g2=F(6-ой и первые 5 без g1) получаем g2
3. берём g3=F(7-ой и предыущую группу без g2) получаем g3
   далее остаётся 4 груза назовём их r1,r2,r3,r4
4. z1=F(g1,g2,g3,r1,r2)
5. z2=F(g1,g2,g3,r1,r3) if (z1=z2) результат z2
6. z3=F(g1,g2,g3,r1,r4) if (z3=z1 или z2) результат z3
7. z4=F(g1,g2,g3,r2,r3) if (z4=z1 или z2 или z3) результат z4
Отредактировано 02.02.2017 20:18 kov_serg . Предыдущая версия .
Re[4]: Средний груз
От: nikholas Россия  
Дата: 03.02.17 05:44
Оценка:
Здравствуйте, kov_serg, Вы писали:

_>Тогда 7.


Можно и за меньшее число операций.
Re: Средний груз
От: StatujaLeha на правах ИМХО
Дата: 03.02.17 06:44
Оценка:
Здравствуйте, nikholas, Вы писали:

1. g1 = F(первые 5). Про g1 можно утверждать, что она по весу ранжируется на 3, 4 или 5-ое место.
2. g2 = F(первые 5 — g1 + 6-ая). Про g2 можно утверждать, что она по весу ранжируется на 3, 4 или 5-ое место.
3. g3 = F(вторые 5 — g2 + 7-ая). Про g2 можно утверждать, что она по весу ранжируется на 3, 4 или 5-ое место.

G = g1, g2, g3 в отсортированной последовательности занимают места 3, 4, 5. Поэтому искомая гирька среди них.
Пусть R = r1, r2, r3, r4 — оставшиеся гирьки.

Если применить операцию к гирькам из G + любым двум из R, то результат будет в G.

Делаем три операции:
1. F(g1, g2, g3, r1, r2)
2. F(g1, g2, g3, r1, r3)
3. F(g1, g2, g3, r3, r4)

Варианты:
1. r1 и r2 весят меньше/больше, чем гирьки из G. Тогда мы увидим, что три последние операции поочередно вернут все гирьки из G. Искомая гирька — на шаге 2.
2. r1 и r2 весят одна меньше, а другая больше, чем гирьки из G. Тогда мы увидим,
— либо на втором шаге результат операции не изменится и тогда искомая гирька у нас в руках.
— либо результат операции на 2-ом шаге изменится, а на 3-ем вернется обратно и тогда искомая гирька у нас в руках.

6 операций.
Re[5]: Средний груз
От: kov_serg Россия  
Дата: 03.02.17 06:45
Оценка: 2 (1)
Здравствуйте, nikholas, Вы писали:

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


_>>Тогда 7.


N>Можно и за меньшее число операций.


Точно за 5 операций можно
1. берём g1=F(первые 5) находим g1
2. берём g2=F(6-ой и первые 5 без g1) получаем g2
3. берём g3=F(7-ой и предыущую группу без g2) получаем g3
   далее остаётся 4 груза назовём их r1,r2,r3,r4
4. z1=F(g1,g2,g3,r1,r2)
5. z2=F(g1,g2,g3,r3,r4) if (z1=z2) то z2
   else (g1,g2,g3)-z1-z2
Отредактировано 03.02.2017 8:21 kov_serg . Предыдущая версия . Еще …
Отредактировано 03.02.2017 8:04 kov_serg . Предыдущая версия .
Отредактировано 03.02.2017 7:03 kov_serg . Предыдущая версия .
Отредактировано 03.02.2017 7:01 kov_serg . Предыдущая версия .
Re[2]: Средний груз
От: kov_serg Россия  
Дата: 03.02.17 06:48
Оценка:
Здравствуйте, StatujaLeha, Вы писали:

Там получается 6 вариантов 2 + 4
пусть
r1<r2<r3<r4
g1<g2<g3
тогда
r1 r2 g1 g2 g3 *F=g1
r1 g1 g2 g3 r3 *F=g2
r1 g1 g2 g3 r4 *F=g2
r2 g1 g2 g3 r3 *F=g2
r2 g1 g2 g3 r4 *F=g2
g1 g2 g3 r3 r4 *F=g3

Вы правы достаточно двух операций

Тогда надо всего 3+2 = 5 пераций достаточно
Отредактировано 03.02.2017 6:59 kov_serg . Предыдущая версия . Еще …
Отредактировано 03.02.2017 6:53 kov_serg . Предыдущая версия .
Re[3]: Средний груз
От: StatujaLeha на правах ИМХО
Дата: 03.02.17 07:38
Оценка:
Здравствуйте, kov_serg, Вы писали:

_>Тогда надо всего 3+2 = 5 пераций достаточно


При такой схеме 6 надо.
1. Берем мы две гирьки из R. Мы же не знаем, как оно выпало: {r1, r2, g1, g2, g3}/{g1, g2, g3, r3, r4} или же {r1, g1, g2, g3, r2}/etc...
2. В обоих вариантах при замене гирьки на втором шаге может произойти смена результата операции. В таком сценарии понятно, что искомая гирька — это либо то, что получили на первом шаге, либо на втором.
Но пока еще нельзя различить между этими двумя гирьками.
Для этого нужна третья операция.
3. Берем еще одну гирьку и смотрим, как изменился результат:
— если это новая гирька из G, то на первом шаге у нас было что-то из {r1, r2, g1, g2, g3}/{g1, g2, g3, r3, r4}
— если это старая гирька из G, то на первом шаге у нас было что-то из {r1, g1, g2, g3, r2}/etc...
Re[4]: Средний груз
От: kov_serg Россия  
Дата: 03.02.17 08:01
Оценка:
Здравствуйте, StatujaLeha, Вы писали:

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


_>>Тогда надо всего 3+2 = 5 пераций достаточно


SL>При такой схеме 6 надо.

SL>1. Берем мы две гирьки из R. Мы же не знаем, как оно выпало: {r1, r2, g1, g2, g3}/{g1, g2, g3, r3, r4} или же {r1, g1, g2, g3, r2}/etc...
SL>2. В обоих вариантах при замене гирьки на втором шаге может произойти смена результата операции. В таком сценарии понятно, что искомая гирька — это либо то, что получили на первом шаге, либо на втором.
SL> Но пока еще нельзя различить между этими двумя гирьками.
SL> Для этого нужна третья операция.
SL>3. Берем еще одну гирьку и смотрим, как изменился результат:
SL> — если это новая гирька из G, то на первом шаге у нас было что-то из {r1, r2, g1, g2, g3}/{g1, g2, g3, r3, r4}
SL> — если это старая гирька из G, то на первом шаге у нас было что-то из {r1, g1, g2, g3, r2}/etc...
Вы правы
Re[5]: Средний груз
От: StatujaLeha на правах ИМХО
Дата: 03.02.17 08:05
Оценка:
Здравствуйте, kov_serg, Вы писали:

_>Вы правы


Осталось выяснить, можно ли сделать за 5
Re[6]: Средний груз
От: kov_serg Россия  
Дата: 03.02.17 08:20
Оценка:
Здравствуйте, StatujaLeha, Вы писали:

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


_>>Вы правы


SL>Осталось выяснить, можно ли сделать за 5

SL>

Нет проблем. Можно за 5
// gcc a.cpp && ./a.out  | sort -u

#include <stdio.h>

enum { N=7 };

void show(int *x) { for(int i=0;i<N;i++) printf(" %d",x[i]); printf("\n"); }
void swp(int *x,int i,int j) { int t; t=x[i]; x[i]=x[j]; x[j]=t; }
void swpc(int *x,int *p,int a,int b) { if (x[p[a]]>x[p[b]]) swp(p,a,b); }
int  mean5(int *x,int i0,int i1,int i2,int i3,int i4) { int p[5]={i0,i1,i2,i3,i4}; for(int i=1;i<5;i++) for(int j=i;j<5;j++) swpc(x,p,i-1,j); return p[2]; }

void check(int *x) {
    int i,j,k,y[N],a[5],z[4];
    for(i=0;i<N;i++) y[i]=x[i];
    i=mean5(y,0,1,2,3,4); a[0]=y[i]; swp(y,i,5);
    i=mean5(y,0,1,2,3,4); a[1]=y[i]; swp(y,i,6);
    i=mean5(y,0,1,2,3,4); a[2]=y[i];
    j=0;for(i=0;i<5;i++) if (y[i]!=a[2]) z[j++]=y[i];
    a[3]=z[0]; a[4]=z[1]; i=mean5(a,0,1,2,3,4);
    a[3]=z[2]; a[4]=z[3]; j=mean5(a,0,1,2,3,4);
    if (i!=j) {
        for(k=0;k<3;k++) if (k!=i && k!=j) break;
        i=k;
    }
    printf("%d\n",a[i]);
}

void test(int *x,int i) {
    check(x);
    for(int j=i+1;j<N;j++) { swp(x,i,j); test(x,i+1); swp(x,i,j); }
}

int main(int argc,char** argv) {
    int x[N];
    for(int i=0;i<N;i++) x[i]=i;
    test(x,0);
    return 0;
}
Re[6]: Средний груз
От: nikholas Россия  
Дата: 07.02.17 19:44
Оценка:
Здравствуйте, kov_serg, Вы писали:

_>Точно за 5 операций можно

_>
_>1. берём g1=F(первые 5) находим g1
_>2. берём g2=F(6-ой и первые 5 без g1) получаем g2
_>3. берём g3=F(7-ой и предыущую группу без g2) получаем g3
_>   далее остаётся 4 груза назовём их r1,r2,r3,r4
_>4. z1=F(g1,g2,g3,r1,r2)
_>5. z2=F(g1,g2,g3,r3,r4) if (z1=z2) то z2
_>   else (g1,g2,g3)-z1-z2
_>


Это красивое решение, но может быть можно за меньшее число операций?
Re[2]: Средний груз
От: StatujaLeha на правах ИМХО
Дата: 07.02.17 21:45
Оценка:
Здравствуйте, StatujaLeha, Вы писали:

SL>Делаем три операции:

SL>1. F(g1, g2, g3, r1, r2)
SL>2. F(g1, g2, g3, r1, r3)
SL>3. F(g1, g2, g3, r3, r4)

Я тут подумал, после первых трех надо делать не такие операции.
Мы знаем, что гирьки g1, g2, g3 находятся на 3,4 и 5 позициях. Надо выяснить, какая из них находится на позиции 4.

Так же у нас есть гирьки r1, r2, r3, r4, две из которых по весу меньше, чем gi, а две больше.

Взвешивания:
1. F(g1, g2, g3, r1, r2) in [g1, g2, g3]
2. F(g1, g2, g3, r3, r4) in [g1, g2, g3]

Варианты:
1. r1, r2 < g1, g2, g3 или g1, g2, g3 < r1, r2. Тогда результат первой операции будет отличаться от результата второй. Значит, искомая гирька та, которая не выпала в качестве результата.
2. r1 < g1, g2, g3 < r2 или r2 < g1, g2, g3 < r1. Тогда результат первой операции не будет отличаться от результата второй. Значит искомая гирька та, что выпала дважды в операциях.

Итого 5 операций.
Re: Средний груз
От: rg45 СССР  
Дата: 11.02.17 00:22
Оценка:
Здравствуйте, nikholas, Вы писали:

N>Имеется гирьки одинаковые по форме но попарно различные по весу.

N>За одну операцию можно найти средннюю по весу из 5 гирек.
N>За какое наименьшее число таких операций можно найти среднюю по весу из 7 гирек?

Решение за 5 попыток:

1. Первыми тремя попытками определяем трех "кандидатов" (три гирьки наиболее близкие к медиане) и четырех "аутсайдеров". Думаю, алгоритм понятен: после каждой попытки отставляем очереднго "победителя" в сторону и заменяем его новой гирькой.

2. Разбиваем четверых "аутсайдеров" на две пары произвольным образом и выполняем еще две попытки, комбинируя образовавшиеся пары "аутсайдеров" с тройкой "кандидатов". Если в результате этих двух попыток избранной окажется одна и та же гирька — она и есть искомая средняя. Если же выбор пал на две разные гирьки, то искомой средней является ни та, ни другая, а третья.
--
Не можешь достичь желаемого — пожелай достигнутого.
Re[2]: Средний груз
От: nikholas Россия  
Дата: 13.02.17 12:54
Оценка: 1 (1)
Здравствуйте, rg45, Вы писали:

R>Решение за 5 попыток:


Можно и за 4 операции...
Re[3]: Средний груз
От: kov_serg Россия  
Дата: 13.02.17 13:25
Оценка:
Здравствуйте, nikholas, Вы писали:

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


R>>Решение за 5 попыток:


N>Можно и за 4 операции...


Только если можно пилить грузы попалам или делать копию
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.