На второй неделе проклятия я начал решать Ханойскую башню в качестве разминки. Это игра, в которой вы должны переместить диски из башни 1 в последнюю башню. В этой игре есть несколько правил, которым вы должны следовать, они просты. Это:
- Вы можете переместить только один диск
- Вы не можете поместить больший диск на меньший диск
Чтобы решить ханойскую башню, первое, что вы должны проверить, является ли количество дисков четным или нечетным; решение зависит от него; если ответ состоит в том, что количество дисков четное, порядок ходов отличается от хода, если количество дисков нечетное. минимальное количество ходов для сборки башни равно 2^n — 1, где n — общее количество дисков.
Если количество дисков нечетное, первое, что нужно сделать, это передать первый диск в последнюю башню, затем мы передаем следующий диск во вторую башню; если мы не можем пройти следующий диск башни 1, мы делаем последнюю башню первой, а вторую - третьей…. Это звучит запутанно, но идея состоит в том, чтобы сделать что-то вроде перехода к последней башне, а затем начать возвращаться. Это будет что-то вроде того, что вы начинаете с первой башни и начинаете возвращаться, поэтому, когда вы находитесь на первой башне, вы переходите на третью, а на третьей переходите на вторую…. Решение игры с 3-мя дисками будет таким:
Move: 0 the tower 1 is 1,2,3 the tower 2 is the tower 3 is Move: 1 the tower 1 is 2,3 the tower 2 is the tower 3 is 1 Move: 2 the tower 1 is 3 the tower 2 is 2 the tower 3 is 1 Move: 3 the tower 1 is 3 the tower 2 is 1,2 the tower 3 is Move: 4 the tower 1 is the tower 2 is 1,2 the tower 3 is 3 Move: 5 the tower 1 is 1 the tower 2 is 2 the tower 3 is 3 Move: 6 the tower 1 is 1 the tower 2 is the tower 3 is 2,3 Move: 7 the tower 1 is the tower 2 is the tower 3 is 1,2,3
Если количество дисков четное, порядок ходов немного меняется, ходы будут вправо, поэтому первый ход - передать первый диск во вторую башню, а затем передать второй диск в третью. башню и делайте то же самое, пока у вас не останется больше ходов, поэтому следующее, что нужно сделать, это изменить порядок дисков, как мы сделали с нечетными; но разница в том, чтобы изменить порядок... Решение игры с 4 дисками:
Move: 0 the tower 1 is 1,2,3,4 the tower 2 is the tower 3 is Move: 1 the tower 1 is 2,3,4 the tower 2 is 1 the tower 3 is Move: 2 the tower 1 is 3,4 the tower 2 is 1 the tower 3 is 2 Move: 3 the tower 1 is 3,4 the tower 2 is the tower 3 is 1,2 Move: 4 the tower 1 is 4 the tower 2 is 3 the tower 3 is 1,2 Move: 5 the tower 1 is 1,4 the tower 2 is 3 the tower 3 is 2 Move: 6 the tower 1 is 1,4 the tower 2 is 2,3 the tower 3 is Move: 7 the tower 1 is 4 the tower 2 is 1,2,3 the tower 3 is Move: 8 the tower 1 is the tower 2 is 1,2,3 the tower 3 is 4 Move: 9 the tower 1 is the tower 2 is 2,3 the tower 3 is 1,4 Move: 10 the tower 1 is 2 the tower 2 is 3 the tower 3 is 1,4 Move: 11 the tower 1 is 1,2 the tower 2 is 3 the tower 3 is 4 Move: 12 the tower 1 is 1,2 the tower 2 is the tower 3 is 3,4 Move: 13 the tower 1 is 2 the tower 2 is 1 the tower 3 is 3,4 Move: 14 the tower 1 is the tower 2 is 1 the tower 3 is 2,3,4 Move: 15 the tower 1 is the tower 2 is the tower 3 is 1,2,3,4
Решение на JavaScript будет примерно таким:
var tower1 = [1, 2, 3, 4];
var tower2 = [];
var tower3 = [];
var solve = function(discs, src, aux, dest, count) {
console.log(`Move: ${count}`);
console.log(`the tower 1 is ${tower1}`);
console.log(`the tower 2 is ${tower2}`);
console.log(`the tower 3 is ${tower3}`);
if(tower3.length === discs){
return tower3;
}
if(discs % 2 !== 0) {
if(src[0] < dest[0] || !dest[0]) {
dest.unshift(src[0]);
src.splice(0, 1);
count ++;
return aux[0]? solve(discs, aux, dest, src, count) : solve(discs, src, aux, dest, count);
} else if (src[0] < aux[0] || !aux[0]) {
aux.unshift(src[0]);
src.splice(0, 1);
count ++;
return dest[0]? solve(discs, dest, src, aux, count) : solve(discs, src, aux, dest, count);
} else {
return solve(discs, dest, src, aux, count)
}
} else {
if (src[0] < aux[0] || !aux[0]) {
aux.unshift(src[0]);
src.splice(0, 1);
count ++;
return dest[0]? solve(discs, dest, src, aux, count) : solve(discs, src, aux, dest, count);
} else if(src[0] < dest[0] || !dest[0]) {
dest.unshift(src[0]);
src.splice(0, 1);
count ++;
return aux[0]? solve(discs, aux, dest, src, count) : solve(discs, src, aux, dest, count);
} else {
return solve(discs, aux, dest, src, count)
}
}
};
console.log(solve(4, tower1, tower2, tower3, 0))
Чтобы решить эту проблему, у нас есть три башни, которые представляют собой массивы деревьев, первая из которых будет src, вторая будет вспомогательной, которая поможет нам удерживать некоторые диски, пока мы не переместим другие, и последний будет пунктом назначения. Мы будем считать ходы, чтобы узнать, является ли это лучшим решением. Важно использовать рекурсию для решения проблемы, используя рекурсию, нам нужно изменить порядок параметров, которые мы собираемся передать методу. Мы должны проверить, является ли оно нечетным или четным, чтобы решить проблему, оба могут быть решены одинаково, но решение не будет лучшим, поэтому нам нужно разделить его. Когда длина башни 3 равна количеству дисков задачи, тогда мы знаем, что у нас есть ответ.
