VPF::Задача на мышление! - Форум программистов

Dobermann

Дата 22.3.2010, 17:49 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 992
Регистрация: 7.1.2008

Есть 3 сосуда:
Первый - на 3 литра
2ой - 7 литров
3ий - 10 литров

1ый и 2ой - пустые. В 3ем - 10 литров воды(жидкости/без разницы)

Задача:
Нужно за 5 шагов сделать так, чтобы во 2ом и 3ем сосуде было по 5 литров!
Условие: сосуды бесформенные(к примеру: один тонкий и длинный, другой квадратный и почти плоский, третий вообще под землей smile

ну или как то так smile

)! Т.е. внешне нельзя сравнить залитую жидкость по объему! Только известно, что 1ый и 2ой пустые,а 3ий(10литровый) залит полностью...

Добавлено через 20 секунд
Сам нихрена не решил... smile

Lim4

Дата 22.3.2010, 18:51 (ссылка)

(голосов:6)

Загрузка ...

Не под ковром

Профиль
Группа: Участник
Сообщений: 66
Регистрация: 4.7.2008

За пять шагов не получилось. smile

1с.(3)    0     |   0  |  3  |  0  |  3  |  0  |  1  |  1  |  3  |  0
2с.(7)    0     |   7  |  4  |  4  |  1  |  1  |  0  |  7  |  5  |  5
3с.(10)  10   |   3  |  3  |  6  |  6  |  9  |  9  |  2  |  2  |  5

Это сообщение отредактировал(а) Lim4 - 22.3.2010, 18:56

Dobermann

Дата 22.3.2010, 19:34 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 992
Регистрация: 7.1.2008

Тут по-моему математически за 5 шагов никак не сделать... =\

SelenIT

Дата 24.3.2010, 19:28 (ссылка)

(голосов:1)

Загрузка ...

баг форума

Профиль
Группа: Завсегдатай
Сообщений: 3996
Регистрация: 17.10.2006
Где: Pale Blue Dot

Похоже, вариант Lim4 оптимален.

По крайней мере, вот такая наскоро сделанная проверялка

Код


var volumes = [10,7,3]; // Объемы сoсудов
var checked = {} // Сюда будем заносить встреченные расклады и номер шага, где они получены.
                 // Если расклад достигался в других цепочках за меньшее число шагов,
                 // значит, проверяемая цепочка заведомо неоптимальна,
                 // рассматривать ее дальше нет смысла.

function move(path) {
    var index = 'c'+ path[path.length-1].join('|');
    if (!checked[index] || (checked[index] > path.length) || (index == 'c5|5|0')) {
        if (index == 'c5|5|0') {
            document.write(path.join(' &rarr; ') + ' &mdash; <b>решение!</b> ('+(path.length-1)+' шагов)<br>');
        }
        else {
            checked[index] = path.length;
            var current = path[path.length-1];
            for (var i=0; i<3; i++) {
                for (var j=0; j<3; j++) {
                    if (i!=j) {
                        var moved = Math.min(current[i], volumes[j] - current[j]);
                        if (moved > 0) {
                            var path1 = [];
                            for (var s=0; s<path.length; s++) {
                                path1[s] = path[s];
                            }
                            path1[path1.length] = [];
                            for(var n=0; n<3; n++) {
                                if (n==i) path1[path1.length-1][n] = current[i]-moved;
                                else if (n==j) path1[path1.length-1][n] = current[j]+moved;
                                else path1[path1.length-1][n] = current[n];
                            }
                            move(path1);
                        }
                    }
                }
            }
        }
    }
}

move([[10,0,0]]);

лучшего варианта не находит. Вариант, который нашел я сам, на шаг хуже (скрипт выдает его третьим). Правда, аналитически обосновать пока не выходит... smile

Возможно, условие подразумевает другое определение шага (напр. "вылить из 7-литровика сколько получится в трехлитровик, а остальное - в 10-литровик" считается одним шагом;).

--------------------

Осторожно! Данный юзер и его посты содержат ДГМО! Противопоказано лицам с предрасположенностью к зонеризму!

pycha

Дата 24.3.2010, 20:22 (ссылка)

(нет голосов)

Загрузка ...

главный анастазиолог

Профиль
Группа: Участник
Сообщений: 239
Регистрация: 20.6.2008
Где: Украина

мда задачка, никогда меня так не напрягало нерешение задачи

--------------------

ищу хакера со знанием компьютера длятехкт

Lim4

Дата 25.3.2010, 11:32 (ссылка)

(нет голосов)

Загрузка ...

Не под ковром

Профиль
Группа: Участник
Сообщений: 66
Регистрация: 4.7.2008

SelenIT, ухтышка smile

chaos

Дата 25.3.2010, 15:33 (ссылка)

(голосов:1)

Загрузка ...

Серийный программист

Профиль
Группа: Завсегдатай
Сообщений: 2979
Регистрация: 7.7.2004
Где: Екатеринбург

иль как-то так

0    0    10
3    0    7
0    3    7
3    3    4
0    6    4
3    6    1
2    7    1
2    0    8
0    2    8
3    2    5
0    5    5

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Флейм \| Следующая тема »