数组入门题笔记及改错"/>
数组入门题笔记及改错
文章目录
- 1.小鱼倒背数1427
- 2.门外树1047
- 3.旗鼓相当的对手 1728
- 4.立方体切割5729
- 5.彩票摇奖2550
- 6.幻方2615
- 7.显示屏5730
- 8.梦中统计1554
- 9.珠心算2141
- 10.爱与愁心痛1614
- 11.筛子和概率最大数2911
- 12.开灯1161
- 13.蛇形方阵5731
数组入门集合
2.4.5采用使用 计数排序****桶排序
计数排序针对整数，利用数组下标确定元素位置
什么是桶排序非整数
计数排序需要根据原始数列的取值范围，创建一个统计数组，用来统计原始数列中每一个可能的整数值所出现的次数
1.小鱼倒背数1427
1.普通数组输入，反向输出
#include<stdio.h>
int main()
{int a[100]={1},i=0,cnt=0;for(i=0; ;i++)//这里可以没有判断条件{cnt++;scanf("%d",&a[i]);if(a[i]==0)//但是在内部需要加上出循环的条件break;}for(i=cnt-2;i>=0;i--)//跳过最后一个1元素0 ，进行输出{--cnt;printf("%d ",a[i]);}return 0;
}
2.手打栈。先入的后出
#include<stdio.h>
int a[101];//第一个数存储在a[i]中，多开空间防治越界
int top=0,c;//top表示栈顶
int main()
{while(1)//未知数组长度可以一直输入，if条件输出{scanf("%d",&c);if(c==0) break;//非0数,执行完次循环后结束a[++top]=c;//存储在a数组中，这里不能使用top++,解释①}while(top!=0){printf("%d ",a[top--]);}return 0;
}
①首先明白自增运算符操作，不懂可以看三。3。自增运算符
例：3 65 23 5 34 1 30 0
逆序后是 30 1 34 5 23 65 3
(top++)是被赋值 0 1 2 3 4 …个位置，逆序输出的是 ：65 23 5 34 1 30 0,不会省略调0
(++top)自增是第 1 2 3 4 5 …个位置，所以逆序输出：3 65 23 5 34 1 30，会自动排挤 逆序后a[0] 也就是第一位的0
3.数组指针
int a[101];
int c;
int *p=a;//指针指向数组首元素地址
int main()
{while(1){scanf("%d",&c);if(c==0) break;//输入数据p++;//指针不断指向下一个元素地址，自增运算见上*p=c;//指针指向输入的数据地址}while(p!=a)//不要从头输出，逆序的第二个开始{printf("%d ",*(p--));}return 0;
}
这里p!=a,相当于上面的++top,
2.门外树1047
#include<stdio.h>
int a[10001];
int u=0,v=0,cnt=0;
int main()
{int l,m,i,j;scanf("%d %d",&l,&m);for(i=0;i<=l;i++)//注意<=,两边的树也要被标记a[i]=1; while(m--)//输入3行{scanf("%d %d",&u,&v);for(i=u;i<=v;i++)//排除包括两边的这一范围的树a[i]=0;}for(i=0;i<=l;i++)//包括两边，计数被标记{if(a[i]==1)cnt++;}printf("%d",cnt);return 0;
}
绝对值函数：abs()、cabs()、fabs()、labs()
3.旗鼓相当的对手 1728
1.认真审题，二维数组
对于这道题第一思路繁琐是
cnt=1; cnt<m-1;
将第 [i] 每一个元素都和 [i+cnt] 行每一个元素比较，cnt++; 反正只有 3 咧，可以列出 9 种情况，但是觉得限制条件不够完善，假如有3列，第2行会和第4行比较，但是第四行随机数，无法比较，而且比较较为麻烦
，这里出现审题错误：
每一科成绩的分差都不大于 5，而不是任意两科成绩差
确实想的有点繁琐
简化：只有3列，那么就按行输入，表明 列
j=i+1;j<m;j++这样每一门成绩都进行了比较，也好限制。
#include<stdio.h>
#include<math.h>
int m=100,i=0,j=0;
int sum[1001],n=0;
int cnt=0,a[1001][3];
int main()
{scanf("%d",&m);for(i=0;i<m;i++){scanf("%d%d%d",&a[i][0],&a[i][1],&a[i][2]);sum[i] = a[i][0] + a[i][1] + a[i][2];}for(i=0;i<m;i++){for(j=i+1;j<m;j++){if( abs(a[i][1]-a[j][1]) <= 5 && abs(a[i][2]-a[j][2]) <= 5 &&abs(a[i][3]-a[j][3]) <= 5 &&abs(sum[i]-sum[j])<=10)cnt++;} }printf("%d",cnt);return 0;
}
2.结构体
思路和二维数组一样
typedef struct S
{int a,b,c,sum;
};int main()
{int m,i,j,cnt=0;scanf("%d",&m);struct S s[m];for(i=0;i<m;i++){scanf("%d%d%d",&s[i].a,&s[i].b,&s[i].c);s[i].sum=s[i].a + s[i].b + s[i].c;}for(i=0;i<m;i++){for(j=i+1;j<m;j++){if(abs(s[i].a-s[j].a)<=5 &&abs(s[i].b-s[j].b)<=5 &&abs(s[i].c-s[j].c)<=5 &&abs(s[i].sum-s[j].sum) <= 10)//就是表达形式换样了cnt++;}}printf("%d",cnt);return 0;
}
4.立方体切割5729
1.一维数组
思路很简单，仔细阅读题目就是求两个立方体体积差
#include<stdio.h>
#include<math.h>
int main()
{int w,x,h,w1,x1,h1;//(1≤w,x,h≤20)int q=0;//(q≤100)int i,j,k,v,v2[100],n;scanf("%d%d%d",&w,&x,&h);//长方体长宽高scanf("%d",&q);//行int a[3],b[3];for(i=0;i<q;i++){scanf("%d%d%d",&a[0],&a[1],&a[2]);scanf("%d%d%d",&b[0],&b[1],&b[2])//两点坐标}v=w*x*h;for(i=0;i<q;i++){w1=b[0]-a[0]+1;x1=b[1]-a[1]+1;h1=b[2]-a[2]+1;//因切割也包括他们本身，所以需要加一v2[i]=v-w1*x1*h1;printf("%d",v2[i]); }return 0;
}
2.和种树一样，对切割的地方进行标记
int main()
{int a[21][21][21],cnt=0,n,p,b,c;int x,y,z,x1,y1,z1,i,j,k;scanf("%d%d%d",&p,&b,&c);for(i=0;i<p;i++){for(j=0;j<b;j++){for(k=0;k<c;k++){a[i][j][k]=1;//标记所有数}}}scanf("%d",&n);while(n--)//n行{scanf("%d%d%d%d%d%d",&x,&y,&z,&x1,&y1,&z1); //两个坐标for(i=x;i<=x1;i++){for(j=y;j<=y1;j++){for(k=z;k<=z1;k++){a[i][j][k]=0;//标记被消灭的格子}}} }for(i=0;i<p;i++){for(j=0;j<b;j++){for(k=0;k<c;k++){if(a[i][j][k]==1){cnt++;//数}}}}printf("%d",cnt);return 0;}
5.彩票摇奖2550
初步想法是存中奖要求数，与n一 一比较，再相等则对应位置加一，但是比较太费时间
题解：计数排序
根据彩票随机出数的范围，标记已经出数的位置1作为评判基准
如果小明买的彩票位置也为1，中彩票等级加1，
初始化 等级数组 ，逆序输出
#include<stdio.h>
int f[33],p[10],n,m,i,j;
int main()
{scanf("%d",&n);for(i=0;i<7;i++){scanf("%d",&m);//打印得奖序号f[m]=1;//标记得奖序号}//标记彩票数 for(i=0;i<n;i++){int sum=0;//中奖等级for(j=0;j<7;j++){scanf("%d",&m);//买的彩票序号if(f[m]==1)sum++;//是中奖序号，自加记录中奖等级位置 }p[sum]++;//中奖等级自加 }for(i=7;i>0;i--)printf("%d ",p[i]);//从等级大的开始输出（逆序） return 0;
}
6.幻方2615
初步想法是翻译四个条件，但是
暴力输出浪费空间
1.暴力解题
#include<stdio.h>
int a[40][40] = { 0 };
int main() {int n,i,j;scanf("%d",&n); int p = 1; // 填到几了int x, y; // 上一个点坐标while (p <= n * n) {//方阵最大数作为标准if (p == 1) a[x=1][y=n / 2 + 1] = p++;//将 1写在第一行的中间,后面要用到x,y坐标，所以需要标记x,y的位置 else if (x == 1 && y != n) a[x=n][++y] = p++;//p自加 else if (x != 1 && y == n) a[--x][y = 1] = p++;else if (x == 1 && y == n) a[++x][y] = p++;else if (x != 1 && y != n)if (a[x - 1][y + 1] == 0)a[--x][++y] = p++;elsea[++x][y] = p++;}for (i = 1; i <= n; ++i) {for (j = 1; j <= n; ++j)printf("%d ",a[i][j]);printf("\n");}
}
2.大佬想法，同样是找位置，自增填数，右上角有数就填，没数就正下方
int n,x,y,i,j,a[40][40];int main(){scanf("%d",&n);x=1,y=(n+1)/2;for(i=1;i<=n*n;i++){//行，每个元素 a[x][y]=i;if(!a[(x-2+n)%n+1][y%n+1]) x=(x-2+n)%n+1,y=y%n+1;//右上角，一定要有取余防止溢出else x=x%n+1;//数学运算，正下，行加一，列不变}for(i=1;i<=n;i++){for(j=1;j<=n;j++){printf("%d ",a[i][j]);}printf("\n");}
}
7.显示屏5730
同样是打表
初步想法是分别将0-9包装成函数，实现起来4倍数列的 . 又需要一个函数，觉得有点麻烦
大佬简化：将0—9放在三维数组中，
a[10][5][3]，10个数组，分别有5行3列
输出时，s=0; b[i][s+j]; s+=4;<-这里放.中间的
wowowowow
#include<stdio.h>
#include<string.h>
char c[10][5][4]= //打表数组，坑1
{//打表"XXX",//0"X.X","X.X","X.X","XXX","..X",//1,右对齐，坑2"..X","..X","..X","..X","XXX",//2"..X","XXX","X..","XXX","XXX",//3"..X","XXX","..X","XXX","X.X",//4"X.X","XXX","..X","..X","XXX",//5"X..","XXX","..X","XXX","XXX",//6"X..","XXX","X.X","XXX","XXX",//7"..X","..X","..X","..X","XXX",//8"X.X","XXX","X.X","XXX","XXX",//9"X.X","XXX","..X","XXX"
},ans[10][1000];//答案数组，坑4
int main(){//主函数int n,a,s=0,i,j,k;//s表示当前位置scanf("%d",&n);while(n--){scanf("%1d",&a);//坑3，小技巧%1d只读一位for(i=0;i<5;i++)//复制for(j=0;j<3;j++)ans[i][s+j]=c[a][i][j];for(i=0;i<5;i++) ans[i][s+3]='.';//一列'.'，坑5s+=4;//往后挪}for(i=0;i<5;i++){//输出for(j=0;j<s-1;j++) printf("%c",ans[i][j]);//注意范围，坑6printf("\n");}return 0;//华丽结束
}
8.梦中统计1554
初步想法：枚举范围内元素依次放在数组内，在分别
取个十百位，二层for循环，和 i 比较a[j]++;
缺点：限制位数
正确解题1：枚举，统计位。
#include<stdio.h>
#include<stdlib.h>
int main()
{int a[10]={0},i,j;int M,N;scanf("%d%d",&M,&N);for(i=M;i<=N;i++){for(j=i;j;j/=10)//①j=129 ②j=j/10=12 a[j%10]++; //①j%10=9②j=2 }for(i=0;i<10;i++){printf("%d ",a[i]);} return 0;
}
for循环，最后一个条件，进入循环最后执行
算法思想就是不断取%个位丢掉 / 个位，得到每一位的数
9.珠心算2141
注意要输出数量而不是几种。。。
比如1+4=5与2+3=5是一种不是两种！
我第一次只注意到了不重复加同一个数而没有注意种类！
#include<stdio.h>
#include<stdlib.h>
int a[101],i,j,k,b[101];
int n,s=0;
int main()
{scanf("%d",&n);//正整数集合//b数组是判断重复 for(i=0;i<n;i++){scanf("%d",&a[i]);}for(i=0;i<n;i++)for(j=i;j<n;j++)for(k=0;k<n;k++)if(k!=i && k!=j && i!=j &&a[i]+a[j]==a[k]&& b[k]==0 )//三个都不相等！！！坑了我半小时{s++;b[k]=1;//标记已经被加过，剔除该数 } printf("%d",s);/*其中有多少个数，恰好等于集合中另外两个（不同的）数之和*/return 0;
}10.爱与愁心痛1614
初步想法是m个求和，不断放在数组中，载给数组排序，取出最小值
优化只需要不断比较找到最小值，不需要排序，解法同数组中找到最小3个数
#include<stdio.h>
int n,m,i,j;
int a[10001],t=0,min=10000;
int main()
{scanf("%d%d",&n,&m);for(i=0;i<n;i++){scanf("%d",&a[i]);}for(i=0;i<n-m+1;i++)//加的有n-m+1个和{for(j=i;j<i+m;j++)//i后面3个求和{t += a[j];}if(t<min) //比较找最小值{min=t;}t=0;}
11.筛子和概率最大数2911
初步思路
//算出所有和，统计所有和出现次数，输出次数最多的，
//如果最多次数有好几个数，输出最小的
但是和用的是三维数组，浪费空间较严重，而且后期不知道如何输出次数最多的数：
优化其实 求和 和1统计次数 可以同步进行s[i+j+k]++;
又是找到最大值 max=0;s[i]>max;max=s[i];选择最大赋值，下标就是和！
#include<stdio.h>
int main()
{int s1,s2,s3,i,j,k,min=1000,max=1,maxl=0,z;scanf("%d%d%d",&s1,&s2,&s3);int s[10000];for(i=1;i<=s1;i++){for(j=1;j<=s2;j++){for(k=1;k<=s3;k++){s[i+j+k]++;//算出所有和，统计所有和出现次数，if(s[i+j+k]>max)max=s[i+j+k];}} }
//如果最多次数有好几个数，输出最小的 for(i=1;i<=max;i++){if(s[i]>maxl){maxl=s[i];//找到最大次数 z=i;//标记最大和 }}printf("%d",z); return 0;
}
12.开灯1161
**初步想法**创建数组标记已经开的的地方，输出没有标记过的地方，但是不清楚输出检阅范围
解决输出可以不要限制范围，for循环内部找 到了直接break输出即可
int a[2000001],n,p,i;
double x,y,j;
int main(){scanf("%d",&n);for(i=1;i<=n;i++){scanf("%f%d",&x,&y);for(j=1;j<=y;++j){p=j*x;//已经关系过的下标if(a[p]==0) a[p]=1;else a[p]=0;//标记}}for(i=1;;i++){//就是这里！可以不要范围限制！if(a[i]==1){printf("%d\t",i);break;//break掉就是破出for循环}}return 0;
}
解题2:位运算，异或
异或就是把两个数拆成二进制，一位一位比较，某一位上一样返回0，不一样返回1；
一个数异或它本身得到0（因为每一位都一样全部返回0）；
因为只有一盏灯是开的，也就是说，其他编号出现的次数都是成对的，异或完都是0，剩下的那一个与0异或得它本身。因此最后ans就是结果。
#include<stdio.h>
#define f(i,j,n) for(i=j;i<=n;i++)
int main()
{int n,t,i,ans=0;double a; //为了保险我们还是开doublescanf("%d",&n);int p;while(n--){scanf("%lf%d",&a,&t);//注意是输入是%lf !! f(i,1,t){p=i*a;//在这里运算p，进行强制类型转化，不要在定义时强制，否则输出为0 ans^=p;//对进行标记过的地方进行位运算 }}printf("%d",ans); //输出ans即可return 0;
}
13.蛇形方阵5731
初步想法写出四个外部基本规律，问题在于如何运用到循环中，i,j,x,y 关系
优化解法
1.既然有四个规律，那就给蛇，如果越界或位置被占，不断转头，不断向右转
2.不断打印上下左右，t=1,t++;以 t<nn 作为最终判断结束打印。打印条件是旁边位置为空且不出界*
1.*越界或位置被占*，不断转头，不断向右
#include<stdio.h>
int a[15][15],i,j;//记录输出的数组
int pos[4][2]={0,1,1,0,0,-1,-1,0};//改变位置的数组//0表示右，1表示下，2表示左，3表示上
int main(){//主函数int n=0,x=1,y=1,d=0;//初始化scanf("%d",&n); for(i=1;i<=n*n;i++){//遍历a[x][y]=i;//赋值int tx=x+pos[d][0],ty=y+pos[d][1];//核心代码，解释见上if(tx<1||tx>n||ty<1||ty>n||a[tx][ty]) d=(d+1)%4;//出界或旁边位置被占，转弯 x+=pos[d][0],y+=pos[d][1];}for(i=1;i<=n;i++){//输出for(j=1;j<=n;j++) printf("%3d",a[i][j]);//注意%3dif(i<n) printf("\n");}return 0;//华丽结束
}
2.不断打印上下左右，t=1,t++;以 t<n*n 作为最终判断结束打印。打印条件是旁边*位置为空且不出界*
#include<stdio.h>
int n,a[9][9];
int main()
{int x=1,y=1,m=1,i,j;//x,y定位，m标记数据scanf("%d",&n);a[x][y]=m;//先把第一行第一个位置放1 while(m<n*n)//以m作为判断条件，避免了使用i的尴尬 {while(a[x][y+1]==0 && y+1<=n)//右 {y++; m++;a[x][y] = m; }while(a[x+1][y] == 0 && x+1<=n)//下{x++; m++;a[x][y] = m;} while(a[x][y-1] == 0 && y-1>=1)//左 {y--; m++;a[x][y] = m;}while(a[x-1][y] == 0 && x-1>=1)//上 {x--; m++;a[x][y]=m;}} for(i=1;i<=n;i++){for(j=1;j<=n;j++){printf("%3d",a[i][j]);//坑。个位，十位对齐 }printf("\n");} return 0;
}
更多推荐
数组入门题笔记及改错
发布评论