2022-6-27

如何回形遍历一个矩阵：

 1 #include  
 2 #include 
 3 #include 
 4 #include <string.h>
 5 int m,n;
 6 int main()
 7 {
 8     scanf("%d%d",&m,&n);
 9     int a[m][n],visit[m][n];
10     memset(visit,0,sizeof(visit));
11     for(int i=0;i){
12         for(int j=0;j){
13             scanf("%d",&a[i][j]);
14         }
15     }
16     int b[m*n];
17     int cnt=0,i=0,j=0;
18     int *p=0;
19     b[0]=a[0][0],visit[0][0]=1;
20     while(cnt1){
21         while(j1 && visit[i][j+1]==0)cnt++,p=*(a+i)+j+1,b[cnt]=*p,j++,visit[i][j]=1;
22         while(i1 && visit[i+1][j]==0)cnt++,p=*(a+i+1)+j,b[cnt]=*p,i++,visit[i][j]=1;
23         while(j>0 && visit[i][j-1]==0)cnt++,p=*(a+i)+j-1,b[cnt]=*p,j--,visit[i][j]=1;
24         while(i>0 && visit[i-1][j]==0)cnt++,p=*(a+i-1)+j,b[cnt]=*p,i--,visit[i][j]=1;
25     }
26     for(int i=0;i){
27         printf("%d ",b[i]);
28     }
29     return 0;
30 }

矩阵乘法：（三重循环，我这个脑子太好使了）

 1 #include  
 2 #include 
 3 #include 
 4 #define MOD 10000007//为防止溢出，取模 
 5 int a[7][7],b[7][7],c[7][7],x,y,z;//x,y是数组a的行数和列数,数组b的列数和行数 
 6 void createRandomArray(){
 7     x=rand()%5,y=rand()%5,z=rand()%5;
 8     for(int i=0;i){
 9         for(int j=0;j){
10             a[i][j]=rand()%100;//矩阵中所有元素均在0-100之间 
11         }
12     }
13     for(int i=0;i){
14         for(int j=0;j){
15             b[i][j]=rand()%100;
16         }
17     }
18 }
19 void calArrayMultiply(){
20     for(int i=0;i)
21         for(int j=0;j)
22             for(int k=0;k)
23                 c[i][j]+=a[i][k]*b[k][j]%MOD;//用三重循环实现乘法 
24 }
25 int main()
26 {
27     srand((unsigned)time(NULL));
28     createRandomArray();
29     calArrayMultiply();
30     puts("以下是第一个矩阵：");
31     for(int i=0;i){
32         for(int j=0;j){
33             printf("%3d",a[i][j]);
34         }
35         puts("");
36     }
37     puts("以下是第二个矩阵：");
38     for(int i=0;i){
39         for(int j=0;j){
40             printf("%3d",b[i][j]);
41         }
42         puts("");
43     }
44     puts("以下是结果矩阵：");
45     for(int i=0;i){
46         for(int j=0;j){
47             printf("%-8d",c[i][j]);
48         }
49         puts("");
50     }
51     return 0;
52 }

插入（双指针）：

 1 //第五题
 2 #include  
 3 #include 
 4 #include 
 5 int main()
 6 {
 7     int a[11];
 8     for(int i=0;i<10;i++)a[i]=rand()%20;
 9     for(int i=0;i<10;i++){
10         int minindex=i;
11         for(int j=i;j<10;j++){
12             if(a[j]<a[minindex]){
13                 minindex=j;
14             }
15         }
16         if(i!=minindex){
17             int t=a[i];
18             a[i]=a[minindex];
19             a[minindex]=t;
20         }
21     }
22     printf("插入前:\n");
23     for(int i=0;i<10;i++){
24         printf("%d ",a[i]);
25         if(i==6)printf("\n");
26     }
27     printf("\n");
28     int x;
29     scanf("%d",&x);
30     int i;
31     for(i=0;i<10;i++){
32         if(x>=a[i]){
33             if(i==9){
34                 printf("在这：%d\n",i);
35                 break;
36             }
37             else{
38                 if(x<=a[i+1])break;
39             }
40         }
41     }
42     int p1,p2=x;
43     for(int j=i+1;j<11;j++){
44         p1=a[j];
45         a[j]=p2;
46         p2=p1;
47     }
48     printf("\n插入后:\n");
49     for(int j=0;j<11;j++){
50             printf("%d ",a[j]);
51             if(j==6)printf("\n");
52     }
53     return 0;
54 }

矩阵旋转：（用好下标变换）

 1 #include  
 2 #include 
 3 #include <string.h> 
 4 #include 
 5 void zhuan(int n,int angle,int a[][5],int b[][5]){
 6     if(angle==90){
 7         for(int i=0;i){
 8             for(int j=0;j){
 9                 b[i][j]=a[j][n-i-1];
10             }     
11         }
12     }
13     else if(angle==180){
14         for(int i=0;i){
15             for(int j=0;j){
16                 b[i][j]=a[n-i-1][n-1-j];
17             }     
18         }
19     }
20     else{
21         for(int i=0;i){
22             for(int j=0;j){
23                 b[i][j]=a[n-j-1][i];
24             }     
25         }
26     } 
27 }
28 int main()
29 {
30     //int x;
31     //puts("请输入想要的阶数：");
32     //scanf("%d",&x);
33     //x=5;
34     int a[5][5],b[5][5];
35     puts("这是没有旋转的矩阵:");
36     for(int i=0;i<5;i++){
37         for(int j =0;j<5;j++){
38             a[i][j]=rand()%20;
39             printf("%-3d",a[i][j]);
40         }
41         puts("");
42     }
43     puts("请输入要旋转的角度:");
44     int angle;
45     scanf("%d",&angle);
46     puts("");
47     zhuan(5,angle,a,b);
48     puts("这是旋转以后的矩阵:");
49     for(int i=0;i<5;i++){
50         for(int j =0;j<5;j++){
51             printf("%-3d",b[i][j]);
52         }
53         puts("");
54     }
55     return 0;
56 }

 多源最短路（在曼哈顿图中）（无例题）（使用BFA，队列）：

　　操作的地图要有两个特点：既可以表示结果中所要的最短距离，又能记录这个点是否走过，那就全部memset为一个特殊的数-1（这里一定要专门设计一个结果图，不能只用最初的图，让最初的图承担三个责任，它哪里做的到啊（表示举例，判重，记录最初信息）（非要做的话，你可以想象，如果发现一个点可以是起点，那就改变其值为0，这个0要如何与其他没去过的点的0区分呢，如果另开一个数组那就可以区分了，起点处是0，没去过的地方是-1）），这就是个特殊的判重技巧：另开一个数组。

　　本题代码有个bug，不知道为什么输出结果有误，以后改过来。

　　题目：

　　code：

 1 #include
 2 using namespace std;
 3 int n,m,a[100][100],b[100][100];
 4 struct node{int x,y;};
 5 int hx[]={0,0,1,-1};
 6 int hy[]={1,-1,0,0};
 7 queue q;
 8 void bfs(){
 9     while(q.size()){
10         node t=q.front();
11         q.pop();
12         for(int i=0;i<4;i++){
13             int dx=t.x+hx[i],dy=t.y+hy[i];
14             if(dx>=0&&dx=0&&dy1){
15                 b[dx][dy]=b[t.x][t.y]+1,q.push({dx,dy});
16             }
17         }
18     } 
19 }
20 int main(){
21     cin>>n>>m;
22     memset(b,-1,sizeof(b));
23     for(int i=0;i){
24         for(int j=0;j){
25             cin>>a[i][j];
26             if(a[i][j]==1)q.push({i,j}),b[i][j]=0;
27         }
28     }
29     bfs();
30     for(int i=0;i){
31         for(int j=0;j){
32             cout<" ";
33         }
34         cout<<endl;
35     }
36     return 0; 
37 }

 一道很有趣的条件纠缠问题：

某侦察队接到一项紧急任务，要求在A、B、C、D、E、F六个队员中尽可能多地挑若干人，但有以下限制条件：

1)A和B两人中至少去一人；

2)A和D不能一起去；

3)A、E和F三人中要派两人去；

4)B和C都去或都不去；

5)C和D两人中去一个；

6)若D不去，则E也不去。

试编写一个程序，输出问应当让哪几个人去？

解法：用深搜遍历每一种可能性。将约束条件写成函数即可求出所有合理的解法，在解法中找到去的人数最多的那一种即可。

code:(本题是C语言程序设计实践的上机题，所以使用C语言写成)（注意约束条件是怎么写的，不要把”ABC有两个人去“写成“ABC都去不行”||“ABC都不去不行”||“A去了BC没去”……这种形式，这一看头都快破掉了，然而我最初就真是这么写的……我这个脑子呦）

再注意一点：DFS是有模板的，虽说不要求背诵模板，但起码要有个大致的印象，比如本题中前6层的递归都是在找答案，到了第七层就输出答案，所以出口的条件就是if(n==6)

对了，if的出口之后记得加一个else,这是必备的，否则就会数组越界。

 1 #include 
 2 #include <string.h>
 3 int a[6];//0表示没去，1表示去了
 4 int right(){
 5     if(a[0]==0&&a[1]==0)return 0;
 6     
 7     if(a[0]&&a[3])return 0;
 8     
 9     int cnt=0;
10     if(a[0])cnt++;
11     if(a[4])cnt++;
12     if(a[5])cnt++;
13     if(cnt!=2)return 0;
14     
15     if((a[1]==0&&a[2])||(a[1]&&a[2]==0))return 0;
16     
17     int cnt1=0;
18     if(a[2])cnt1++;
19     if(a[3])cnt1++;
20     if(cnt1!=1)return 0;
21     
22     if(!a[3]&&a[4])return 0;
23     
24     return 1;
25 }
26 void dfs(int p){
27     if(p==6){
28         if(right()){
29             for(int i=0;i<6;i++)if(a[i])printf("%c去了 ",i+'A');
30             printf("\n");
31         }    
32     }
33     else
34     for(int i=0;i<2;i++){
35         a[p]=i;
36         dfs(p+1);
37     }
38 }
39 int main(int argc, char** argv) {
40     dfs(0);
41     return 0;
42 }

大致模板如下：

 1 void dfs(){
 2     if(到达出口){
 3         出去吧你 
 4     }else{
 5         开探照灯
 6         for(){
 7             if(判越界，判重){
 8                 更新 
 9                 dfs(下一层)
10                 变回来 
11             }
12         } 
13     }
14 }

一道数学题：

我们知道，在10 进制数中有判断整除性的二个简单规则:一个正整数能够被3整除，当且仅当，它的各位数字之和能够被3整除;一个正整数能够被11整除，当且仅当，它的奇数位数字之和与偶数位数字之和的差能够被11整除;现在要问:对于b进制数，具有类似于10进制数的3和11的这种整除性判断的数是什么?具体地，请编写程序，输入进制的基数b,输出最小的可以如上判断整除性的数x和数y，输入输出均采用10 进制数.

示例 :

输入b为10，则自然要输出x为3，y为11; 若输入b为8，则要输出x为7, y为3 (例如8进制数25，按上述规则判断应能够被7和3整除，事实上，8进制数25是10进制数21，能够被7和3整除是显然的) ;若输入b为120，则要输出x为7, y为11 (请自己验证这是对的).

提示:对于10进制数，10-1=9=3*3， 10+1=11， 10进制数n可以一般地表示为:

n=a_k10^k+a_k-110^k-1+ ....+a₁10+a0

保持n不改变数值将10换为10-1和10+1，可以看出3和11可以如上判断整除性的理由.

 思考：如果(b+1)%x==0，这个x就是你要找的；如果（b-1）%y==0，这个y就是你要找的。

code：

 1 #include 
 2 #include <string.h>
 3 int main(int argc, char** argv) {
 4     int b,x=2,y=2;
 5     scanf("%d",&b);
 6     while(1){
 7         if((b-1)%x == 0)break;
 8         x++;
 9     } 
10     while(1){
11         if((b+1)%y == 0)break;
12         y++; 
13     }
14     printf("x=%d  y=%d",x,y);
15     return 0;
16 }