###### tags: `提升程式設計師的面試力`
# 8-1~8-7 .Solutions to Recursion and Dynamic Programming
https://docs.google.com/spreadsheets/d/1DrM4JKn5ew7a7YInKBp66CmI5xityJp46vY24O2gUuI/edit?usp=sharing
## 8.1
```
Triple Step: A child is running up a staircase with n steps and can hop either 1 step, 2 steps, or 3
steps at a time. Implement a method to count how many possible ways the child can run up the
stairs.
```
```
一個孩子正在跑上 n 步的樓梯，可以跳 1 步、2 步或 3 步
一步一步。 實現一種方法來計算孩子可以跑多少種可能的方式
樓梯。
```
```php=
<?php
function CH8_1(int $n){
if($n <= 0) return 1;
if($n <= 1) return 1;
if($n <= 2) return 2;
return CH8_1($n-1)+CH8_1($n-2)+CH8_1($n-3);
}
echo CH8_1(5);
function CH8_1_M(int $n,array &$memo){//memo一定要加上& //超快
if($n <= 0) return 1;
if($n == 1) return 1;
if($n == 2) return 2;
if(isset($memo[$n])) return $memo[$n];//重要
$memo[$n] = CH8_1_M($n-3,$memo)+CH8_1_M($n-2,$memo)+CH8_1_M($n-1,$memo);
return $memo[$n];
}
$temp = array();
echo CH8_1_M($n,$temp);
```
## 8.2
```
Robot in a Grid: Imagine a robot sitting on the upper left corner of grid with r rows and c columns.
The robot can only move in two directions, right and down, but certain cells are "off limits" such that
the robot cannot step on them. Design an algorithm to find a path for the robot from the top left to
the bottom right.
```
```
網格中的機器人：想像一個機器人坐在網格的左上角，有 r 行和 c 列。
機器人只能在兩個方向上移動，向右和向下，但某些單元格是“禁區”，這樣
機器人無法踩到它們。 設計一個算法來找到機器人從左上角到
右下角。
```
```php=
<?php
$array[] = [1,1,1,1,1,1,1];
$array[] = [1,0,1,1,1,1,1];
$array[] = [1,1,0,1,1,1,1];
$array[] = [1,1,1,0,1,1,1];
$array[] = [1,1,1,1,0,1,1];
$array[] = [1,1,1,1,1,0,1];
$array2[] = [1,1,1,1];
$array2[] = [1,1,1,1];
$array2[] = [1,1,1,1];
$array2[] = [1,1,1,1];
function ways(array $array,array $start = [],array $end = [],&$count){
if(count($end) == 0) $end = [(count($array)-1),(count($array[0])-1)];
if(!isset($array[$end[0]][$end[1]])){
return false;
}
if(count($start) == 0) $start = [0,0];
if(!$array[$end[0]][$end[1]] || $end[0] < $start[0] || $end[1] < $start[1]){
return false;
}
// print_r($end);
if($start == $end) $count++;
if(ways($array,$start,[$end[0]-1,$end[1]],$count) || ways($array,$start,[$end[0],$end[1]-1],$count)){
return true;
}
return false;
}
$x = 0;
$start = [];
$end = [];
ways($array2,$start,$end,$x);
echo "<br>".$x."總方法start走到end";
```
## 8.3
```
Magic Index: A magic index in an array A[ 1 .•. n-1] is defined to be an index such that
A[i] = i. Given a sorted array of distinct integers, write a method to find a magic index, if one exists, in
array A.
FOLLOW UP
What if the values are not distinct?
```
```
魔術索引：魔術索引數組 A[1 ... n-1] 被定義為一個索引，使得 A[i] = i。
給定一個由不同整數組成的排序數組，
編寫一個方法來查找一個魔法索引（如果存在）
數組 A。
跟進
如果值不明確怎麼辦？
```
```php=
<?php
$magic = [-40,-20,-1,1,2,3,5,7,9,12,13];//唯一解
$magic = [-10,-5,2,2,2,3,5,7,9,12,13];//兩解
$magic = [-10,-5,1,2,2,3,5,8,9,12,13];//無解
function magicFast(array $array,int $start,int $end){
if($end < $start) return -1;
$mid = floor(($start + $end) / 2);
if($array[$mid] == $mid) return $mid;
$left_index = min($mid-1,$array[$mid]);//優化
$left = magicFast($array,$start,$left_index);
if($left > 0) return $left;
$right_index = max($mid+1,$array[$mid]);//優化
$right = magicFast($array,$right_index,$end);
return $right;
}
function main($array){
return magicFast($array,0,count($array)-1);
}
echo main($magic);
```
## 8.4
```
Power Set: Write a method to return all subsets of a set.
```
```
冪集：編寫一個方法來返回一個集合的所有子集。
```
```php=
<?php
$array = [1,2,3,4,5,6,7,8,9,10];
function powerSet(array $array){
$all = [[]];
foreach ($array as $n) {
foreach ($all as $o) {
array_push($o,$n);
array_push($all,$o);
}
}
return $all;
}
print_r(powerSet($array));
```
## 8.5
```
Recursive Multiply: Write a recursive function to multiply two positive integers without using
the * operator (or / operator). You can use addition, subtraction, and bit shifting, but you should
minimize the number of those operations.
```
```
遞歸乘法：編寫一個遞歸函數來將兩個正整數相乘而不使用
* 運算符（或 / 運算符）。 您可以使用加法、減法和位移，但您應該
盡量減少這些操作的數量。
```
## 8.6
```
Towers of Hanoi: In the classic problem of the Towers of Hanoi, you have 3 towers and N disks of
different sizes which can slide onto any tower. The puzzle starts with disks sorted in ascending order
of size from top to bottom (i.e., each disk sits on top of an even larger one). You have the following
constraints:
(1) Only one disk can be moved at a time.
(2) A disk is slid off the top of one tower onto another tower.
(3) A disk cannot be placed on top of a smaller disk.
Write a program to move the disks from the first tower to the last using Stacks.
```
```
河內塔：在河內塔的經典問題中，你有 3 個塔和 N 個磁盤
可以滑到任何塔上的不同尺寸。 拼圖從按升序排列的磁盤開始
從上到下的大小（即，每個磁盤都位於更大的磁盤之上）。 你有以下
約束：
(1) 一次只能移動一個磁盤。
(2) 一個圓盤從一個塔的頂部滑到另一個塔上。
(3) 磁盤不能放在較小的磁盤上。
編寫一個程序，使用堆棧將磁盤從第一個塔移動到最後一個塔。
```
```php=
<?php
$n = $_GET['n'] ?? 3;
class Tower
{
public $name = '';
public $disk = [];
public $action = 0;
function __construct($name)
{
$this->name = $name;
}
function add($n)
{
$this->disk[] = $n;
}
function moveTopTo(Tower $tower)
{
$top = array_pop($this->disk);
$tower->add($top);
$this->action ++;
}
function moveDisks(int $n, Tower $destination, Tower $buffer)
{
if ($n > 0) {
$this->moveDisks($n - 1, $buffer, $destination);
$this->moveTopTo($destination);
$buffer->moveDisks($n - 1, $destination, $this);
}
}
}
$start = memory_get_usage();
$tower1 = new Tower('first');
$tower2 = new Tower('second');
$tower3 = new Tower('third');
for ($i = 0; $i < $n; $i++) {
$tower1->add($i);
}
$tower1->moveDisks($n,$tower2,$tower3);
print_r($tower1);
print_r($tower2);
print_r($tower3);
```
## 8.7
```
Permutations without Dups: Write a method to compute all permutations of a string of unique
characters.
```
```
沒有重複的排列：編寫一個方法來計算唯一字符串的所有排列
人物。
```
```php=
<?php
function sol($str)
{
if (strlen($str) == 1) {
return combo([], $str);
} else {
$array = sol(substr($str,0, -1));
return combo($array, substr($str, -1));
}
}
function combo(array $strs, $insert_str)
{
$all = [];
if(count($strs) == 0){
$all = [$insert_str];
}
foreach ($strs as $str) {
for ($i = 0; $i < strlen($str); $i++) {
$head = substr($str, 0, $i);
$foot = substr($str, $i, strlen($str) - $i);
$all[] = $head . $insert_str . $foot;
}
$all[] = $str.$insert_str;
}
return $all;
}
print_r(sol("abcde"));
```
## 8.8
```
Permutations with Duplicates: Write a method to compute all permutations of a string whose
characters are not necessarily unique. The list of permutations should not have duplicates.
```
```
Permutations with Duplicates：編寫一個方法來計算一個字符串的所有排列
字符不一定是唯一的。 排列列表不應有重複項。
```
## 8.9
```
Parens: Implement an algorithm to print all valid (i.e., properly opened and closed) combinations
of n pairs of parentheses.
EXAMPLE
Input: 3
Output: (( () ) ) , ( () () ) , ( () ) () , () ( () ) , () () ()
```
```
Parens：實現一個算法來打印所有有效（即正確打開和關閉）的組合
n 對括號。
例子
```
## 8.10
```
Paint Fill: Implement the"paint fill"function that one might see on many image editing programs.
That is, given a screen (represented by a two-dimensional array of colors), a point, and a new color,
fill in the surrounding area until the color changes from the original color.
```
```
油漆填充：實現在許多圖像編輯程序中可能會看到的“油漆填充”功能。
也就是說，給定一個屏幕（由一個二維顏色數組表示）、一個點和一個新顏色，
填充周圍區域，直到顏色從原來的顏色改變。
```
## 8.11
```
Coins: Given an infinite number of quarters (25 cents), dimes (1 O cents), nickels (5 cents), and
pennies (1 cent), write code to calculate the number of ways of representing n cents.
```
```
硬幣：給定無限數量的四分之一（25 美分）、一角硬幣（1 O 美分）、鎳幣（5 美分）和
pennies (1 cent)，編寫代碼來計算表示 n 美分的方式的數量。
```
## 8.12
```
Eight Queens:Write an algorithm to print all ways of arranging eight queens on an 8x8 chess board
so that none of them share the same row, column, or diagonal. In this case, "diagonal" means all
diagonals, not just the two that bisect the board.
```
```
八皇后：編寫一個算法來打印在 8x8 棋盤上排列八個皇后的所有方式
使它們都不共享相同的行、列或對角線。 在這種情況下，“對角線”意味著所有
對角線，而不僅僅是將棋盤一分為二的兩條。
```
## 8.13
```
Stack of Boxes: You have a stack of n boxes, with widths w1
, heights hi
, and depths di
. The boxes
cannot be rotated and can only be stacked on top of one another if each box in the stack is strictly
larger than the box above it in width, height, and depth. Implement a method to compute the
height of the tallest possible stack. The height of a stack is the sum of the heights of each box.
```
```
Stack of Boxes：你有一疊 n 個盒子，寬度為 w1
, 高度你好
, 和深度 di
. 那些盒子
不能旋轉，並且只有在堆疊中的每個盒子都嚴格要求時才能相互堆疊
在寬度、高度和深度上大於其上方的框。 實現一個方法來計算
最高可能堆棧的高度。 堆棧的高度是每個盒子的高度之和。
```
## 8.14
```
Boolean Evaluation: Given a boolean expression consisting of the symbols 0 (false), 1 (true), &
(AND), I (OR), and /\ (XOR), and a desired boolean result value result, implement a function to
count the number of ways of parenthesizing the expression such that it evaluates to result. The
expression should be fully parenthesized (e.g., ( 0) A( 1)) but not extraneously (e.g., ( ( ( 0)) /\ ( 1)) ).
```
```
布爾求值：給定一個由符號 0（假）、1（真）和 & 組成的布爾表達式
(AND)、I (OR) 和 /\ (XOR)，以及所需的布爾結果值 result，實現一個函數
計算將表達式括起來以使其計算為結果的方式的數量。 這
表達式應該被完全括起來（例如， ( 0) A( 1)），但不是多餘的（例如， ( ( ( 0)) /\ ( 1)) ）。
```
Sign in with Wallet
Connect another wallet