如何用迭代法求解 Hanoi 问题
How Solve Iterative Method For Hanoi Problem
我正在尝试使用迭代方法解决河内问题。
我尝试通过使用两个 for 嵌套循环来做到这一点,以便在每个循环中重复 n - 1 个步骤,其中 n 是移动次数。我想我已经通过使用两个 for 很好地提出了这个问题,但我不明白如何在每次通过时更改塔的顺序。
谁能帮我完成这个任务?
inizio 正在启动,
罚款是结束和
supp是支持
#include <stdlib.h>
#include <stdio.h>
void tower_Organizer(int *inizio, int *fine, int *supp);
void hanoi_Iter(int n, int inizio, int fine, int supp);
int main(void){
int n;
printf("%s\n" ,"inserisci un nuero positivo");
scanf("%d", &n);
hanoi_Iter(n, 1, 2, 3);
return 0;
}
void hanoi_Iter(int n, int inizio, int fine, int supp){
for(int i = 1 ; i <= n ; i++){
for(int j = 1 ; j <= i - 1 ; j++){
printf("%d -> %d\n", inizio, fine);
tower_Organizer(&inizio, &fine, &supp);
}
printf("%d -> %d\n", inizio, fine);
tower_Organizer(&inizio, &fine, &supp);
}
}
void tower_Organizer(int *inizio, int *fine, int *supp){
static int count = 1;
int c = count % 6;
switch( c ){
case 0:
*inizio = 1;
*fine = 2;
*supp = 3;
break;
case 1:
*inizio = 1;
*fine = 3;
*supp = 2;
break;
case 2:
*inizio = 2;
*fine = 3;
*supp = 1;
break;
case 3:
*inizio = 1;
*fine = 2;
*supp = 3;
break;
case 4:
*inizio = 3;
*fine = 1;
*supp = 2;
break;
case 5:
*inizio = 3;
*fine = 2;
*supp = 1;
break;
}
count++;
}
步数为 2−1,因此您的嵌套循环无法实现,因为它只会产生 (+1)/2 步。
移动哪个圆盘的逻辑也不像 6 个不同移动的循环那么简单。
有多种方法可以实现迭代解决方案,Wikipedia 上对其中一些进行了说明。但是,此处列出的那些要求您保持每个桩(桩)的状态,因此您可以检查什么构成有效移动。
您还可以查看着法序列号的位模式,并从中得出正确的着法。
下面是后一个想法的实现:
void hanoi(int n, int start, int end, int helper) {
// Create a converter for a pile index (0, 1 or 2) to the identifiers
// that are given as arguments:
int map[] = {start, end, helper};
// Perform as many iterations as there are moves to perform:
for (int last = 1<<n, i = 1; i < last; i++) {
// Use bit pattern of i to determine the source peg.
// First remove and count the trailing 0 bits in i:
int j = i;
int zeroCount = 0;
while (j % 2 == 0) {
j >>= 1;
zeroCount++;
}
// Derive the source pile from that zero-stripped number
int source = (j >> 1) % 3;
// Get next pile as destination
int target = (source + 1) % 3;
// Depending on parity, the source/target pile should be mirrored
if ((n + zeroCount) % 2 == 0) {
source = (3 - source) % 3;
target = (3 - target) % 3;
}
printf("Move from %d to %d\n", map[source], map[target]);
}
}
int main(void) {
int n;
printf("%s\n" ,"Enter a positive number (of discs)");
scanf("%d", &n);
hanoi(n, 1, 2, 3);
return 0;
}
我正在尝试使用迭代方法解决河内问题。 我尝试通过使用两个 for 嵌套循环来做到这一点,以便在每个循环中重复 n - 1 个步骤,其中 n 是移动次数。我想我已经通过使用两个 for 很好地提出了这个问题,但我不明白如何在每次通过时更改塔的顺序。 谁能帮我完成这个任务?
inizio 正在启动, 罚款是结束和 supp是支持
#include <stdlib.h>
#include <stdio.h>
void tower_Organizer(int *inizio, int *fine, int *supp);
void hanoi_Iter(int n, int inizio, int fine, int supp);
int main(void){
int n;
printf("%s\n" ,"inserisci un nuero positivo");
scanf("%d", &n);
hanoi_Iter(n, 1, 2, 3);
return 0;
}
void hanoi_Iter(int n, int inizio, int fine, int supp){
for(int i = 1 ; i <= n ; i++){
for(int j = 1 ; j <= i - 1 ; j++){
printf("%d -> %d\n", inizio, fine);
tower_Organizer(&inizio, &fine, &supp);
}
printf("%d -> %d\n", inizio, fine);
tower_Organizer(&inizio, &fine, &supp);
}
}
void tower_Organizer(int *inizio, int *fine, int *supp){
static int count = 1;
int c = count % 6;
switch( c ){
case 0:
*inizio = 1;
*fine = 2;
*supp = 3;
break;
case 1:
*inizio = 1;
*fine = 3;
*supp = 2;
break;
case 2:
*inizio = 2;
*fine = 3;
*supp = 1;
break;
case 3:
*inizio = 1;
*fine = 2;
*supp = 3;
break;
case 4:
*inizio = 3;
*fine = 1;
*supp = 2;
break;
case 5:
*inizio = 3;
*fine = 2;
*supp = 1;
break;
}
count++;
}
步数为 2−1,因此您的嵌套循环无法实现,因为它只会产生 (+1)/2 步。
移动哪个圆盘的逻辑也不像 6 个不同移动的循环那么简单。
有多种方法可以实现迭代解决方案,Wikipedia 上对其中一些进行了说明。但是,此处列出的那些要求您保持每个桩(桩)的状态,因此您可以检查什么构成有效移动。
您还可以查看着法序列号的位模式,并从中得出正确的着法。
下面是后一个想法的实现:
void hanoi(int n, int start, int end, int helper) {
// Create a converter for a pile index (0, 1 or 2) to the identifiers
// that are given as arguments:
int map[] = {start, end, helper};
// Perform as many iterations as there are moves to perform:
for (int last = 1<<n, i = 1; i < last; i++) {
// Use bit pattern of i to determine the source peg.
// First remove and count the trailing 0 bits in i:
int j = i;
int zeroCount = 0;
while (j % 2 == 0) {
j >>= 1;
zeroCount++;
}
// Derive the source pile from that zero-stripped number
int source = (j >> 1) % 3;
// Get next pile as destination
int target = (source + 1) % 3;
// Depending on parity, the source/target pile should be mirrored
if ((n + zeroCount) % 2 == 0) {
source = (3 - source) % 3;
target = (3 - target) % 3;
}
printf("Move from %d to %d\n", map[source], map[target]);
}
}
int main(void) {
int n;
printf("%s\n" ,"Enter a positive number (of discs)");
scanf("%d", &n);
hanoi(n, 1, 2, 3);
return 0;
}