遞推與遞回
遞回實現指數型列舉
從1~n這n個整數中隨機選取任意多個，輸出所有可能的選擇方案。
#include <iostream>
using namespace std;
int n;
//u代表當前進行的遞回計數，state代表哪些數被選與未選
void dfs(int u, int state){
//達到n時輸出
if(u == n){
for(int i =0; i < n; i++)
if(state >> i & 1)
cout << i + 1 << ' ';
cout << endl;
return;
}
//不選當前數位
dfs(u + 1, state);
//選擇當前數位
dfs(u + 1, state | 1 << u);
}
int main(){
cin >> n;
dfs(0, 0);
return 0;
}
遞回實現組合型列舉
從1~n這n個整數中隨機選出m個，輸出所有可能的選擇方案。
#include <iostream>
using namespace std;
int n, m;
//u代表當前進行的遞回計數，sum代表選取了多少個數，state代表哪些數被選與未選
void dfs(int u, int sum, int state){
//當選不夠m個的時候返回，剪枝處理
if(sum + n - u < m) return;
//當選夠m個的時候輸出
if(sum == m){
for(int i=0; i<n; i++)
if(state >> i & 1)
cout << i + 1 << ' ';
cout << endl;
return;
}
//當前數位被選
dfs(u + 1, sum + 1, state | 1 << u);
//當前數位未選
dfs(u + 1, sum, state);
}
int main(){
cin >> n >> m;
dfs(0, 0, 0);
return 0;
}
遞回實現排列型列舉
把1~n這n個整數排成一行後隨機打亂順序，輸出所有可能的次序。
#include <iostream>
#include <vector>
using namespace std;
int n;
vector<int> path;
//u代表當前進行的遞回計數，state代表哪些數被選與未選
void dfs(int u, int state){
//如果u等於n，則輸出當前的排列
if(u == n){
for(auto x : path) cout << x << ' ';
cout << endl;
return;
}
//對於當前第u位，將未選的數位填入，然後遞回
for(int i=0; i<n; i++)
if(!(state >> i & 1)){
path.push_back(i + 1);
dfs(u + 1, state | (1 << i));
path.pop_back();
}
}
int main(){
cin >> n;
dfs(0, 0);
return 0;
}
費解的開關
你玩過拉燈遊戲嗎？25盞燈排成一個5x5的方形。每個燈都有一個開關，遊戲者可以改變它的狀態。每一步，遊戲者可以改變某一個燈的狀態。遊戲者改變一個燈的狀態會產生連鎖反應；和這個燈上下左右相鄰的燈也要相應地改變狀態。
我們用數位「1」表示驛站開着的燈，用數位「0」表示關着的燈。下面 下麪這種狀態
10111
01101
10111
10000
11011
在改變了最左上角的燈的狀態後將變成：
01111
11101
10111
10000
11011
給定一些遊戲的初始狀態，編寫程式判斷遊戲者是否可能在6步之內使所有的燈都變亮。
我們可以知道對於一些要按的燈，按燈順序不會影響最終燈的狀態。那麼我們可以把這個問題逐行分解，對於第一行我們將可能的按法全部列舉，對於後續行我們的目標就是使得前一行的燈全部按亮。由此判斷可不可以在6次內全部按亮。
#include <iostream>
#include <cstring>
using namespace std;
const int INF = 100000;
//g陣列存放燈的狀態，dx和dy用來表示鄰近燈
char g[10][10];
int dx[5] = {0, -1, 0, 1, 0}, dy[5] = {0, 0, 1, 0, -1};
//turn函數會修改當前燈與周圍燈的狀態
void turn(int x, int y){
for(int i =0; i<5; i++){
int a = x + dx[i], b = y + dy[i];
if(a >= 0 && a < 5 && b >=0 && b < 5){
//g[a][b] = '1' - g[a][b] + '0';
g[a][b] ^= 1;
}
}
}
int work(){
//ans代表可能全亮的最少按燈次數
int ans = INF;
//遍歷第一行可能的按法
for(int k = 0; k<1<<5; k++){
//res代表按燈次數
int res = 0;
char backup[10][10];
memcpy(backup, g, sizeof g);
for(int j=0; j<5; j++)
if(k >> j & 1){
res++;
turn(0, j);
}
//根據當前行出現的滅燈，修改下一行對應位置的燈
for(int i=0; i<4; i++)
for(int j=0; j<5; j++)
if(g[i][j] == '0'){
res++;
turn(i + 1, j);
}
//觀察最後一行燈是否全亮，如果全亮將按燈次數與之前比較
bool is_successful = true;
for(int j=0; j<5; j++)
if(g[4][j] == '0'){
is_successful = false;
break;
}
if(is_successful) ans = min(ans, res);
memcpy(g, backup, sizeof g);
}
if(ans > 6) ans=-1;
return ans;
}
int main(){
int T;
cin >> T;
while(T--){
for(int i=0; i<5; i++) cin >> g[i];
cout << work() << endl;
}
return 0;
}
奇怪的漢諾塔
漢諾塔問題，條件如下：
- 這裏有A、B、C和D四座塔。
- 這裏有n個圓盤，n的數量是恆定的， 且n<=12。
- 每個圓盤的尺寸都不相同。
- 所有圓盤在開始時都堆疊在塔A上，且圓盤尺寸從塔頂到塔底逐漸增大。
- 我們需要將所有的圓盤都從塔A轉移到塔D上。
- 每次可以移動一個圓盤，當塔爲空塔或者塔頂圓盤尺寸大於被移動圓盤時，可將圓盤移至這座塔上。
請你求出將所有圓盤從塔A移動到塔D，所需的最小移動次數是多少。
我們可以將其化爲一個動態規劃問題，對於三階漢諾塔，我們可以將問題描述爲D[n] = DD[n-1] x 2 + 1，即先將前n-1個圓盤移到第二個塔上，再將最後一個圓盤放到第三個塔上（僅一步操作），最後將第二個塔上的圓盤全部移動到第三個塔上。
而對於四階漢諾塔，我們要尋找一個合適的圓盤i，將其上的圓盤先移動到一個塔上，所需移動次數設爲F[i]。然後再將其下的圓盤移動到最後一個塔上，此時就是三階漢諾塔問題，D[n-i]。然後再將前i個圓盤移動到最後塔上，即F[i]。這個合適的圓盤i就是使得移動次數最少的圓盤。
#include <iostream>
#include <cstring>
using namespace std;
int main(){
int d[15], f[15];
d[1] = 1;
for(int i=2; i<=12; i++){
d[i] = 1 + d[i-1] * 2;
}
memset(f, 0x3f, sizeof f);
f[0] = 0;
for(int i=1; i<=12; i++)
for(int j=0; j<i; j++)
f[i] = min(f[i], f[j] * 2 + d[i - j]);
for(int i=1; i<=12; i++) cout << f[i] << endl;
return 0;
}
約數之和
假設現在有兩個自然數A和B，S是的所有約數之和。
請你求出S mod 9901的值是多少。
對於數A，我們可以將其分解成質數的形式，A=，其中是A的質數約數，我們可以修改的大小來獲得不同的約數，對於所有的約數之和我們可以表示爲：
對於每一部分，我們還可以進一步化簡，例如，當是奇數的時候，我們可以化簡爲
其中/代表着整數除法
如果爲偶數，那麼就提出一個即可，這樣利用遞回我們可以加速求解
而對於我們可以利用快速冪進行求解（參考上一部落格位運算）。如下是程式碼實現。
#include <iostream>
using namespace std;
const int mod = 9901;
int qmi(int a, int k){
a %= mod;
int res = 1;
while(k){
if(k & 1) res = res * a % mod;
a = a * a % mod;
k >>= 1;
}
return res;
}
int sum(int p, int k){
if(k==0) return 1;
//如果k是偶數就提出一個P，則k-1變爲奇數
if(k % 2 == 0) return (p % mod * sum(p, k - 1) + 1) % mod;
//如果k是奇數
return (1 + qmi(p, k/2 + 1)) * sum(p, k/2) % mod;
}
int main(){
int A, B;
cin >> A >> B;
int res = 1;
for(int i=2; i<=A; i++){
int s=0;
while(A % i ==0){
s++;
A /= i;
}
if(s) res = res * sum(i, s * B) % mod;
}
if(!A) res = 0;
cout << res << endl;
return 0;
}
分形之城
城市的規劃在城市建設中是個大問題。
不幸的是，很多城市在開始建設的時候並沒有很好的規劃，城市規模擴大之後規劃不合理的問題就開始顯現。
而這座名爲 Fractal 的城市設想了這樣的一個規劃方案，如下圖所示：
當城區規模擴大之後，Fractal 的解決方案是把和原來城區結構一樣的區域按照圖中的方式建設在城市周圍，提升城市的等級。
對於任意等級的城市，我們把正方形街區從左上角開始按照道路標號。
雖然這個方案很爛，Fractal 規劃部門的人員還是想知道，如果城市發展到了等級 N，編號爲 A 和 B 的兩個街區的直線距離是多少。
街區的距離指的是街區的中心點之間的距離，每個街區都是邊長爲 10 米的正方形。
我們可以發現每一等級的城市都是由上一等級城市旋轉平移得到的，所以對於該題，我們可以將n等級的城市進行遞回，從1等級開始處理。
將城市劃分成四個區域，左上、右上、左下、右下四個分割區，根據所在分割區決定上一等級城市該如何旋轉平移。然後再將得到的當前等級城市下的座標，傳遞給下一等級的城市，直至規定等級。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define PLL pair<ll,ll>
PLL calc(ll n,ll m)
{
//邊界結果
if (n==0)
return make_pair(0,0);
//len代表當前等級下城市邊長的一半（移動上一等級城市需要），cnt表示當前等級城市下街道數量的1/4（決定分割區）
ll len=1LL<<(n-1),cnt=1LL<<(2*n-2);
//遞回到最低階城市
PLL pos=calc(n-1,m%cnt);
ll x=pos.first,y=pos.second;
//z表示當前等級城市下，m序號的街道所處的分割區，分爲左上、右上、左下、右下四個分割區，從而決定如何旋轉
ll z=m/cnt;
//根據分割區位置旋轉平移上一等級的街道，其中（x,y）代表上一等級城市下街道的位置
if (z==0)
return make_pair(y,x);
if (z==1)
return make_pair(x,y+len);
if (z==2)
return make_pair(x+len,y+len);
return make_pair(2*len-1-y,len-1-x);
}
int main()
{
//ios::sync_with_stdio(false);
int t;
cin>>t;
while(t--)
{
ll n,a,b;
//這裏n代表當前城市等級，a、b代表兩個街道的序號
cin>>n>>a>>b;
//簡化邊界處理，將序號從0開始
PLL x=calc(n,a-1);
PLL y=calc(n,b-1);
ll dx=x.first-y.first,dy=x.second-y.second;
double ans=(sqrt(dx*dx+dy*dy)*10);
printf("%0.lf\n",ans);
}
return 0;
}
遞回改遞推
用遞推來實現遞回程式碼，需要藉助STL中的棧，計算機本身在處理遞回程式碼的時候也是使用棧來實現的。
在這裏我們通過「遞回實現組合型列舉」來舉例說明，我們首先要把原遞回程式碼劃分位置，用來標記處理過程。通過定義結構體，作爲棧的儲存物件，其中要包含標記位置。主函數中我們回圈取出棧首元素，根據所標記的位置來決定如何處理當前元素，直至棧空。
#include <iostream>
#include <stack>
using namespace std;
int n,m;
struct State{
int pos, u, sum, state;
};
void dfs(int u, int sum, int state){
//0
if(sum + n _ u < m) return;
if(sum == m){
for(int i=0; i<n; i++)
if(state >> i & 1)
cout << i + 1 << ' ';
cout << endl;
return;
}
dfs(u + 1, sum + 1, state | 1 << u);
//1
dfs(u + 1, sum, state);
//2
}
int main(){
cin >> n >> m;
//dfs(0, 0, 0)
stack<State> stk;
stk.push({0, 0, 0});
while(stk.size()){
auto t=stk.yop;
stk.pop();
if(t.pos == 0){
if(t.sum + n - t.u < m) continue;
if(t.sum == m){
for(int i=0; i<n; i++)
if(t.state >> i & 1)
cout << i + 1 << ' ';
cout << endl;
continue;
}
t.pos = 1;
stk.push(t);
stk.push({0, t.u + 1, t.sum + 1, t.state | 1 << t.u});
}
else if(t.pos == 1){
t.pos = 2;//可去掉
stk.push(t);//可去掉
stk.push({0, t.u + 1, t.sum, t.state});
}
else continue;//可去掉
}
return 0;
}
標記位置的方法只是個通用模板，我們可以將得到的遞推繼續優化如下：
#include <iostream>
#include <stack>
using namespace std;
int n,m;
struct State{
int u, sum, state;
};
int main(){
cin >> n >> m;
//dfs(0, 0, 0)
stack<State> stk;
stk.push({0, 0, 0});
while(stk.size()){
auto t=stk.top();
stk.pop();
if(t.sum + n - t.u < m) continue;
if(t.sum == m){
for(int i=0; i<n; i++)
if(t.state >> i & 1)
cout << i + 1 << ' ';
cout << endl;
continue;
}
stk.push({t.u + 1, t.sum, t.state});
stk.push({t.u + 1, t.sum + 1, t.state | 1 << t.u});
}
return 0;
}