当前位置： 首页 > news >正文

做网站一天能接多少单百度快照优化推广

news 2025/7/1 23:29:03
做网站一天能接多少单,百度快照优化推广,今日发生的重大新闻,网站域名注册基本流程目录 汉诺塔递归 汉诺塔子移动次数的计算 牛牛的汉诺塔 选择正常的递归模拟计算子移动次数 根据具体数据得出数学规律 根据递归图得出数学规律 将递归函数转化为递推式 结尾 汉诺塔递归 汉诺塔是一个经典问题，相传在古印度圣庙中，有一种被称为汉…

目录

汉诺塔递归

汉诺塔子移动次数的计算

牛牛的汉诺塔

选择正常的递归模拟计算子移动次数

根据具体数据得出数学规律

根据递归图得出数学规律

将递归函数转化为递推式

结尾

汉诺塔递归

汉诺塔是一个经典问题，相传在古印度圣庙中，有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上，有三根杆(编号A、B、C)，在A杆自下而上、由大到小按顺序放置n个金盘。游戏的目标：把A杆上的金盘全部移到C杆上，并仍保持原有顺序叠好。操作规则：每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一杆上。

汉诺塔以及其衍生问题往往使用递归来求解，也是学习和理解递归很好的老师。

其伪代码如下 

 

Function Hanoi(n,a,b,c)if n==1 thenprint(a+'->'+c)elseHanoi(n-1,a,c,b)print(a+'->'+c)Hanoi(n-1,b,a,c)end if
end Function 
 

定义递归函数hanoi(n,a,b,c)表示将n个盘子从a柱移动到c柱，以b柱为辅助柱。
 

维护定义的含义，内部逻辑先将n-1个盘子从a柱移动到b柱，以c柱为辅助柱。再将最大盘子从a柱移动到c柱，以b柱为辅助柱。最后将n-1个盘子从b柱移动到c柱，以a柱为辅助柱。
 

递归结束出口为n==1时，从a柱移动到c柱，以b柱为辅助柱。
 

C++代码
 

 

#include <iostream>
using namespace std;// 函数声明
void hanoi(int n, char a, char b, char c) {if (n == 1) {cout << a << "->" << c<< endl;return;}hanoi(n-1, a, c, b);cout << a << " -> " << c<< endl;hanoi(n-1, b, a, c);
}

 

汉诺塔子移动次数的计算
 

牛牛的汉诺塔
 

 
链接：登录—专业IT笔试面试备考平台_牛客网 来源：牛客网
 
时间限制：C/C++ 1秒，其他语言2秒
 
空间限制：C/C++ 262144K，其他语言524288K
 
64bit IO Format: %lld
 
题目描述 
 
汉诺塔是一个经典问题，相传在古印度圣庙中，有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上，有三根杆(编号A、B、C)，在A杆自下而上、由大到小按顺序放置n个金盘。游戏的目标：把A杆上的金盘全部移到C杆上，并仍保持原有顺序叠好。操作规则：每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一杆上。
 
汉诺塔以及其衍生问题往往使用递归来求解，也是学习和理解递归很好的老师。
 
 
其伪代码如下
 
Function Hanoi(n,a,b,c)
 
if n==1 then
 
print(a+'->'+c)
 
else
 
Hanoi(n-1,a,c,b)
 
print(a+'->'+c)
 
Hanoi(n-1,b,a,c)
 
end if
 
end Function
 
牛牛很快就理解了代码的意思并且写出了求解汉诺塔的程序，他现在想研究汉诺塔的规律。
 
请你统计以下信息：A->B,A->C,B->A,B->C,C->A,C->B的次数，以及所有移动的总步数。
 
输入描述:
 
仅一行，输入一个正整数n(1≤n≤60)(1 leq n leq 60)(1≤n≤60)表示汉诺塔的层数。
 
输出描述:
 
首先输出6行
 
A->B:XX
 
A->C:XX
 
B->A:XX
 
B->C:XX
 
C->A:XX
 
C->B:XX
 
分别表示每种移动情况出现的次数
 
最后输出一行
 
SUM:XX
 
表示所有移动情况的总和。
 
示例1
 
输入
 
复制3
 
3
 
输出
 
复制A->B:1 A->C:3 B->A:1 B->C:1 C->A:0 C->B:1 SUM:7
 
A->B:1
 
A->C:3
 
B->A:1
 
B->C:1
 
C->A:0
 
C->B:1
 
SUM:7
 
说明
 
伪代码所示算法的移动序列如下：
 
A->C
 
A->B
 
C->B
 
A->C
 
B->A
 
B->C
 
A->C
 
统计：
 
A->B出现1次
 
A->C出现3次
 
B->C出现1次
 
B->A出现1次
 
C->B出现1次
 
总计7次
 

 

选择正常的递归模拟计算子移动次数
 

 

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
LL N = 1000005;
LL MOD = 1e4 + 7;
LL N1 = 10005;void Hanoi(int n, char a, char b, char c, int& count_ab, int& count_ac, int& count_ba, int& count_bc, int& count_ca, int& count_cb) {if (a == 'A' && c == 'B') count_ab++;if (a == 'A' && c == 'C') count_ac++;if (a == 'B' && c == 'A') count_ba++;if (a == 'B' && c == 'C') count_bc++;if (a == 'C' && c == 'A') count_ca++;if (a == 'C' && c == 'B') count_cb++;if (n == 1) {return;} else {Hanoi(n - 1, a, c, b, count_ab, count_ac, count_ba, count_bc, count_ca, count_cb);Hanoi(n - 1, b, a, c, count_ab, count_ac, count_ba, count_bc, count_ca, count_cb);}
}
int main() {int count_ab = 0;int count_ac = 0;int count_ba = 0;int count_bc = 0;int count_ca = 0;int count_cb = 0;char a = 'A', b = 'B', c = 'C';int n;cin>>n;Hanoi(n, a, b, c, count_ab, count_ac, count_ba, count_bc, count_ca, count_cb);int count=count_ab+count_ac+count_ba+count_bc+count_ca+count_cb;cout<<"A->B:"<<count_ab<<endl;cout<<"A->C:"<<count_ac<<endl;cout<<"B->A:"<<count_ba<<endl;cout<<"B->C:"<<count_bc<<endl;cout<<"C->A:"<<count_ca<<endl;cout<<"C->B:"<<count_cb<<endl;cout<<"SUM:"<<count;
}
 

我们可以通过递归关系式来表达这个问题的解法次数。对于n个盘子，移动它们所需的步骤T(n)可以表示为：
 

T(n)=2T(n−1)+1
 

这里的思路是：移动n-1个盘子到临时柱子（这需要T(n-1)步），移动最大的盘子到目标柱子（这需要1步），最后再将n-1个盘子从临时柱子移动到目标柱子上（再次需要T(n-1)步）。
 

我们可以进一步解开这个递归式：
 

  •  
    当n = 1时，只需要移动一次，所以T(1) = 1。
     
  •  
    当n = 2时，T(2) = 2T(1) + 1 = 3。
     
  •  
    当n = 3时，T(3) = 2T(2) + 1 = 7。
     
 

以此类推，我们发现这是一个等比数列的求和问题，其总和公式为：
 

T(n)=2^n−1
 

因此，汉诺塔问题的时间复杂度为O(2^n)。这个复杂度表明了随着盘子数量的增加，需要的移动次数呈指数级增长，这也解释了为什么汉诺塔问题在盘子数量稍多时就变得难以直接通过手动移动来解决。
 

 

当n==60时，时间复杂度是O(2^60)，2^10≈1000=10^3，2^60==2^10*2^10*2^10*2^10*2^10*2^10。也就是六个10^3相乘，等于10^18远远超过10^9，10^9对应的时间大概是1s，这样的递归是一定会超时的。
 

根据具体数据得出数学规律
 

我们将正常递归模拟计算子移动次数的代码进行修改，用来计算前n项的子移动次数数据。
 

 

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
LL N = 1000005;
LL MOD = 1e4 + 7;
LL N1 = 10005;void Hanoi(int n, char a, char b, char c, int& count_ab, int& count_ac, int& count_ba, int& count_bc, int& count_ca, int& count_cb) {if (a == 'A' && c == 'B') count_ab++;if (a == 'A' && c == 'C') count_ac++;if (a == 'B' && c == 'A') count_ba++;if (a == 'B' && c == 'C') count_bc++;if (a == 'C' && c == 'A') count_ca++;if (a == 'C' && c == 'B') count_cb++;if (n == 1) {return;} else {Hanoi(n - 1, a, c, b, count_ab, count_ac, count_ba, count_bc, count_ca, count_cb);Hanoi(n - 1, b, a, c, count_ab, count_ac, count_ba, count_bc, count_ca, count_cb);}}
int main() {char a = 'A', b = 'B', c = 'C';cout<<"     ";cout << setw(8) << "a->b " << setw(8) << "a->c " << setw(8) << "b->a " << setw(8) << "b->c " << setw(8) << "c->a " << setw(8) << "c->b " << setw(8) << "SUM " << endl;for (int i = 1; i <= 20; i++) {int count_ab = 0;int count_ac = 0;int count_ba = 0;int count_bc = 0;int count_ca = 0;int count_cb = 0;Hanoi(i, a, b, c, count_ab, count_ac, count_ba, count_bc, count_ca, count_cb);int count = count_ab + count_ac + count_ba + count_bc + count_ca + count_cb;cout << "n="<<setw(2) << i<<":";cout << setw(7) << count_ab << " ";cout << setw(7) << count_ac << " ";cout << setw(7) << count_ba << " ";cout << setw(7) << count_bc << " ";cout << setw(7) << count_ca << " ";cout << setw(7) << count_cb << " ";cout << setw(7) << count << endl;}}
 

 

//输出a->b    a->c    b->a    b->c    c->a    c->b     SUM
n= 1:      0       1       0       0       0       0       1
n= 2:      1       1       0       1       0       0       3
n= 3:      1       3       1       1       0       1       7
n= 4:      4       3       1       4       2       1      15
n= 5:      4       9       6       4       2       6      31
n= 6:     15       9       6      15      12       6      63
n= 7:     15      31      27      15      12      27     127
n= 8:     58      31      27      58      54      27     255
n= 9:     58     117     112      58      54     112     511
n=10:    229     117     112     229     224     112    1023
n=11:    229     459     453     229     224     453    2047
n=12:    912     459     453     912     906     453    4095
n=13:    912    1825    1818     912     906    1818    8191
n=14:   3643    1825    1818    3643    3636    1818   16383
n=15:   3643    7287    7279    3643    3636    7279   32767
n=16:  14566    7287    7279   14566   14558    7279   65535
n=17:  14566   29133   29124   14566   14558   29124  131071
n=18:  58257   29133   29124   58257   58248   29124  262143
n=19:  58257  116515  116505   58257   58248  116505  524287
n=20: 233020  116515  116505  233020  233010  116505 1048575
 

我们将a->b,a->c,b->a,b->c,c->a,c->b分别记为1,2,3,4,5,6。
 

我们希望找出前后项的规律，很容易发现，同一个n中，1号等于4号，3号等于6号。
 

因此我们将数据截取出1,2,3,5四列数据。做法很简单，只需要简单修改代码即可。
 

 

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
LL N = 1000005;
LL MOD = 1e4 + 7;
LL N1 = 10005;void Hanoi(int n, char a, char b, char c, int& count_ab, int& count_ac, int& count_ba, int& count_bc, int& count_ca, int& count_cb) {if (a == 'A' && c == 'B') count_ab++;if (a == 'A' && c == 'C') count_ac++;if (a == 'B' && c == 'A') count_ba++;if (a == 'B' && c == 'C') count_bc++;if (a == 'C' && c == 'A') count_ca++;if (a == 'C' && c == 'B') count_cb++;if (n == 1) {return;} else {Hanoi(n - 1, a, c, b, count_ab, count_ac, count_ba, count_bc, count_ca, count_cb);Hanoi(n - 1, b, a, c, count_ab, count_ac, count_ba, count_bc, count_ca, count_cb);}}
int main() {char a = 'A', b = 'B', c = 'C';cout << "     ";cout << setw(8) << "a->b ";cout << setw(8) << "a->c ";cout << setw(8) << "b->a ";
//    cout << setw(8) << "b->c ";cout << setw(8) << "c->a ";
//    cout << setw(8) << "c->b ";cout << setw(8) << "SUM " << endl;for (int i = 1; i <= 20; i++) {int count_ab = 0;int count_ac = 0;int count_ba = 0;int count_bc = 0;int count_ca = 0;int count_cb = 0;Hanoi(i, a, b, c, count_ab, count_ac, count_ba, count_bc, count_ca, count_cb);int count = count_ab + count_ac + count_ba + count_bc + count_ca + count_cb;cout << "n=" << setw(2) << i << ":";cout << setw(7) << count_ab << " ";cout << setw(7) << count_ac << " ";cout << setw(7) << count_ba << " ";
//        cout << setw(7) << count_bc << " ";cout << setw(7) << count_ca << " ";
//        cout << setw(7) << count_cb << " ";cout << setw(7) << count << endl;}}
 

 

//输出a->b    a->c    b->a    c->a     SUM
n= 1:      0       1       0       0       1
n= 2:      1       1       0       0       3
n= 3:      1       3       1       0       7
n= 4:      4       3       1       2      15
n= 5:      4       9       6       2      31
n= 6:     15       9       6      12      63
n= 7:     15      31      27      12     127
n= 8:     58      31      27      54     255
n= 9:     58     117     112      54     511
n=10:    229     117     112     224    1023
n=11:    229     459     453     224    2047
n=12:    912     459     453     906    4095
n=13:    912    1825    1818     906    8191
n=14:   3643    1825    1818    3636   16383
n=15:   3643    7287    7279    3636   32767
n=16:  14566    7287    7279   14558   65535
n=17:  14566   29133   29124   14558  131071
n=18:  58257   29133   29124   58248  262143
n=19:  58257  116515  116505   58248  524287
n=20: 233020  116515  116505  233010 1048575
 

我们希望由上面的数据找出前后项的关系，我们对a->b,a->c,b->a,c->a重新进行编号，分别记为1,2,3,4。
 

我们需要用的n-1项的1,2,3,4号数据推导出n项的1,2,3,4号数据。
 

找规律的思路是，我们可以先关注n项的1号数据，看n-1项的某一号数据是否可以单独推导出n项的1号数据。1对1的关系。如果1对1的关系找不到，那就找n-1项的多号数据是否可以推导出1号数据，以此类推。
 

 

先关注n项1号与n-1项一对一的关系。
 

当n==7时，1号等于n==6的（2号*2-3），等于（3号*2+3）。
 

当n==8时，1号等于n==7的（2号*2-4），等于（3号*2+4）。
 

当n==9时，1号等于n==8的（2号*2-4），等于（3号*2+4）。
 

当n==10时，1号等于n==9的（2号*2-5），等于（3号*2+5）。
 

很容易发现递推公式，n项的1号等于n-1项的（2号*2-n/2）或者等于（3号*2+n/2）。
 

找到1号的递推式，我们接着找2号的递推式。
 

 

先关注n项2号与n-1项一对一的关系。
 

当n==7时，2号等于n==6的（1号*2+1）。
 

当n==8时，2号等于n==7的（1号*2+1）。
 

当n==9时，2号等于n==8的（1号*2+1）。
 

当n==10时，2号等于n==9的（1号*2+1）。
 

很容易发现递推公式，n项的2号等于n-1项的（2号*2+1）。
 

找到2号的递推式，我们接着找3号的递推式。
 

 

先关注n项3号与n-1项一对一的关系。
 

当n==7时，3号等于n==6的（1号*2-3）。
 

当n==8时，3号等于n==7的（1号*2-3）。
 

当n==9时，3号等于n==8的（1号*2-4）。
 

当n==10时，3号等于n==9的（1号*2-4）。
 

很容易发现递推公式，n项的3号等于n-1项的（1号*2-（n-1）/2）。
 

找到3号的递推式，我们接着找4号的递推式。
 

 

先关注n项4号与n-1项一对一的关系。
 

当n==7时，4号等于n==6的（3号*2）。
 

当n==8时，4号等于n==7的（3号*2）。
 

当n==9时，4号等于n==8的（3号*2）。
 

当n==10时，4号等于n==9的（3号*2）。
 

很容易发现递推公式，n项的4号等于n-1项的（3号*2）。
 

接着我们就可以利用递推式直接求前后项的数据。
 

 

其实我们可以发现，上述的前后项关系不仅仅是上述的几种，例如n项的1号等于n-1项的（1号+2号），n项的3号等于n-1项的（1号+4号）等等。我们知道的是这些推导公式都可以推导出前后项关系，得到递推式。
 

 

#include<bits/stdc++.h>
using namespace std;
using LL=long long;
int main(){int n;cin>>n;vector<vector<LL>> a(n+1,vector<LL>(4));a[1][1]=1;for(int i=2;i<=n;i++){a[i][0]=a[i-1][1]+a[i-1][2];a[i][1]=a[i-1][0]*2+1;a[i][2]=a[i-1][3]*2+(i-1)/2;a[i][3]=a[i-1][2]*2;}cout<<"A->B:"<<a[n][0]<<endl;cout<<"A->C:"<<a[n][1]<<endl;cout<<"B->A:"<<a[n][2]<<endl;cout<<"B->C:"<<a[n][0]<<endl;cout<<"C->A:"<<a[n][3]<<endl;cout<<"C->B:"<<a[n][2]<<endl;cout<<"SUM:"<<a[n][0]*2+a[n][1]+a[n][2]*2+a[n][3]<<endl;
}
 

根据递归图得出数学规律
 

 

 

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main() {int n;cin >> n;LL count_ab = 0, count_ac = 0, count_ba = 0, count_bc = 0, count_ca = 0, count_cb = 0;LL length = 1;for (int i = 1; i <= n; i++) {if (i != 1)length *= 2;if (i % 2 == 1) {LL tempcount = length / 3;count_ac += tempcount;count_cb += tempcount;count_ba += tempcount;LL tempcount1 = length % 3;if (tempcount1 == 1) {count_ac++;} else {count_ac++;count_cb++;}} else {LL tempcount = length / 3;count_ab += tempcount;count_bc += tempcount;count_ca += tempcount;LL tempcount1 = length % 3;if (tempcount1 == 1) {count_ab++;} else {count_ab++;count_bc++;}}}cout << "A->B:" << count_ab << endl;cout << "A->C:" << count_ac << endl;cout << "B->A:" << count_ba << endl;cout << "B->C:" << count_bc << endl;cout << "C->A:" << count_ca << endl;cout << "C->B:" << count_cb << endl;cout << "SUM:" << count_ab + count_ac + count_ba + count_bc + count_ca + count_cb << endl;
}
 

将递归函数转化为递推式
 

 

 

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main() {int n;cin >> n;vector<vector<LL>> dp(3,vector<LL>(7));dp[1][2] = 1;for (int i = 2; i <= n; i++) {dp[2][1] = dp[1][2] + dp[1][3];dp[2][2] = dp[1][1] + dp[1][4] + 1;dp[2][3] = dp[1][1] + dp[1][5];dp[2][4] = dp[1][2] + dp[1][6];dp[2][5] = dp[1][6] + dp[1][3];dp[2][6] = dp[1][5] + dp[1][4];dp[1][1] = dp[2][1];dp[1][2] = dp[2][2];dp[1][3] = dp[2][3];dp[1][4] = dp[2][4];dp[1][5] = dp[2][5];dp[1][6] = dp[2][6];}cout << "A->B:" << dp[1][1] << endl;cout << "A->C:" << dp[1][2] << endl;cout << "B->A:" << dp[1][3] << endl;cout << "B->C:" << dp[1][4] << endl;cout << "C->A:" << dp[1][5] << endl;cout << "C->B:" << dp[1][6] << endl;cout << "SUM:" << dp[1][1] + dp[1][2] + dp[1][3] + dp[1][4] + dp[1][5] + dp[1][6] << endl;
}
 

结尾
 

最后，感谢您阅读我的文章，希望这些内容能够对您有所启发和帮助。如果您有任何问题或想要分享您的观点，请随时在评论区留言。
 

 

同时，不要忘记订阅我的博客以获取更多有趣的内容。在未来的文章中，我将继续探讨这个话题的不同方面，为您呈现更多深度和见解。
 

 

谢谢您的支持，期待与您在下一篇文章中再次相遇！





http://www.dinnco.com/news/13462.html






相关文章：


  • 
公安互联网站备案信息嘉兴seo排名外包

    • 

  • 
怎样做打赏网站近期国内热点新闻事件

    • 

  • 
做网站除了广告还有什么收入的网络推广的几种方式

    • 

  • 
广东省建设部网站百度竞价排名规则

    • 

  • 
南昌专业网站建设百度分析

    • 

  • 
泰州网站开发公司济南优化网站关键词

    • 

  • 
南京网站改版手机营销软件

    • 

  • 
公司管理seo外链代发

    • 

  • 
小公司做网站多少钱直通车推广怎么做

    • 

  • 
杭州网站建设找思创网络免费开通网站

    • 

  • 
动态背景设置网站工厂管理培训课程

    • 

  • 
黑龙江公司网站开发seo这个职位是干什么的

    • 

  • 
2021手机能看的网站广告公司名字

    • 

  • 
济南360做网站电话seo搜索引擎专员

    • 

  • 
兰州市政建设集团网站百度信息流账户搭建

    • 

  • 
那个网站做网编好cps广告是什么意思

    • 

  • 
dw怎么做网站跳转网站产品推广

    • 

  • 
如何做php网站最好的网络推广方式

    • 

  • 
使用公网ip做网站地址广告策划公司

    • 

  • 
深圳网站设计比较好的公司网站seo诊断报告

    • 

  • 
有创意营销型网站建设济宁百度推广电话

    • 

  • 
html商城网站模板下载成人速成班有哪些专业

    • 

  • 
帮做ppt网站什么是网站优化

    • 

  • 
社交网站建设竞价托管一般多少钱

    • 

  • 
拿了网赌代理后怎样做自己的网站强化防疫指导

    • 

  • 
人妖手术怎么做的视频网站爱网站关键词挖掘

    • 

  • 
兰州百度网站建设google搜索引擎入口下载

    • 

  • 
广州app开发网站建设seo网站免费优化软件

    • 

  • 
做网站二级域名随便用吗2023上海又出现疫情了

    • 

  • 
纯div+css做网站简洁版培训机构不退钱最怕什么举报

    •