Marbles in Three Baskets 程序的实现

Question

Problem Description
Each of three baskets contains a certain number of marbles. You may move from one basket into another basket as many marbles as are already there, thus doubling the quantity in the basket that received the marbles. You must find a sequence of moves that will yield the same number of marbles in the three baskets. Moreover, you must achieve the goal in the smallest possible number of moves. Your program must also recognize the case in which there is no such sequence of moves.

Input
Each line of the input file will contain data for one instance of the problem: three positive integers, with one blank space separating adjacent integers. The three integers represent the initial numbers of marbles in the three baskets. The sum of the three integers will be at most 60.

Output
The output will begin with the initial configuration from the input. Thereafter, on successive lines, the number of marbles in the respective baskets will be printed after each move, concluding with the line in which the three numbers are identical. As stated above, the goal must be achieved in the smallest possible number of moves. (The correct output is not unique, however. There may be different sequences of moves which achieve the goal correctly in the smallest possible number of steps.) If there is no sequence of moves to achieve the goal, only the initial configuration will be printed. Each integer in the output will be right-justified in a field of width 4. Each instance of the problem will be concluded by a line of 12 equal signs.

Sample Input
6 7 11
15 18 3
5 6 7

Sample Output
6 7 11
6 14 4
12 8 4

8 8 8

15 18 3
12 18 6

12 12 12

5 6 7

Answer 1

以下回答参考 皆我百晓生、券券喵儿 等免费微信小程序相关内容作答，并由本人整理回复。

# 读取数据
input <- readLines("data.txt")
n <- length(input)
basket <- matrix(0, nrow=n+1, ncol=3)

for(i in 1:n) {
  basket[i] <- c(strsplit(input[[i]], " ")[[1]])
}

basket <- as.matrix(basket[, 1:3])

# 找到最小步数
min_steps <- 999
best_move <- NULL

# 初始化
basket[1, ] <- rep(0, 3)
steps <- 0

while(all(basket[1, ] == basket[2, ])) {
  # 将当前状态复制一份
  temp_basket <- copy(basket)
  
  # 检查是否满足条件
  if(!is.na(temp_basket[2, ])) {
    # 移动至下一个篮子
    basket[2, ] <- temp_basket[2, ]
    steps <- steps + 1
    
    # 更新最小步数和最优解
    min_steps <- min(min_steps, steps)
    best_move <- c(basket[1, ], temp_basket[2, ])
  }
  
  # 清空当前篮子
  basket[2, ] <- rep(0, 3)
  
  # 增加一步
  steps <- steps + 1
}

请注意，这段代码是基于给定的数据文件 data.txt 的。在运行之前，请确保已经将该文件保存为 .txt 文件，并将其放在与脚本相同的目录中。

此外，为了验证代码的正确性，您可以尝试使用以下示例输入：

input <- c("6 7 11",
           "15 18 3",
           "5 6 7")

basket <- matrix(0, nrow=length(input)+1, ncol=3)

for(i in 1:length(input)) {
  basket[i] <- strsplit(input[[i]], " ")[[1]]
}

basket <- as.matrix(basket[, 1:3])

min_steps <- 999
best_move <- NULL

while(all(basket[1, ] == basket[2, ])) {
  temp_basket <- copy(basket)
  
  if(!is.na(temp_basket[2, ])) {
    basket[2, ] <- temp_basket[2, ]
    steps <- steps + 1
    
    min_steps <- min(min_steps, steps)
    best_move <- c(basket[1, ], temp_basket[2, ])
  }
  
  basket[2, ] <- rep(0, 3)
  
  steps <- steps + 1
}

print(paste("Minimum Steps:", min_steps))
print(best_move)