3.数组和字符串
程序员文章站
2022-06-07 14:39:23
...
数组
- 逆序输出
#include<stdio.h> #define maxn 1000000 int a[maxn]; int main() { int x, n=0; // 输入 while(scanf("%d", &x) == 1) a[n++] = x; // 输出 for(int i=n-1; i>=1; i--){ printf("%d ", a[i]); } printf("%d\n", a[0]); return 0; }-
a[n++]，首先赋值a[n]=x，然后执行n=n+1 - 对于变量n，n++和++n都会给n加1，但当它们用在一个表达式中时，行为有所差别：n++会使用加1的值计算表达式，而++n会使用加1后的值计算表达式
- 比较大的数组尽量声明在main函数外，否则程序可能无法运行
-
- 开灯问题
n盏灯，第1个人把所有灯打开，第2个人按下所有编号为2的倍数的开关（这些灯将被关掉），第3个人按下所有编号为3的倍数的开关（其中关掉的灯将被打开，开着的灯将被关掉），依此类推。一共有k个人，问最后有哪些灯开着？
输入n和k，输出开着的灯的编号。k<=n<=1000。#include<stdio.h> #include<string.h> #define maxn 1010 int a[maxn]; int main() { int n, k, first = 1; // 数组a初始化为0 memset(a, 0, sizeof(a)); scanf("%d%d", &n, &k); // 模拟让每个人去按开关 for(int i=1; i<=k; i++){ for(int j=1; j<=n; j++){ if(j%i == 0){ a[j] = !a[j]; } } } // 输出 for(int i=1; i<=n; i++){ if(a[i]){ // 输出时第一个数字前无空格 if(first){ first = 0; }else{ printf(" "); } printf("%d", i); } } printf("\n"); return 0; }memset(a, 0, sizeof(a));的作用是把数组初始化为0，定义在string.h中。 - 蛇形填数
在nn方阵里填入1，2，…，nn，要求填成蛇形。n<=8。
这道题的思路值得好好思考。#include<stdio.h> #include<string.h> #define maxn 20 #define maxm 20 int a[maxn][maxm]; int main() { int n, x=0, y=0, tot = 0; scanf("%d", &n); memset(a, 0, sizeof(a)); tot = a[0][y=n-1] = 1; // 赋值过程 while(tot < n*n) { // 先向下走 while(x+1<n && !a[x+1][y]) { a[++x][y] = ++tot; } // 向左走 while(y-1>=0 && !a[x][y-1]) { a[x][--y] = ++tot; } // 向上走 while(x-1>=0 && !a[x-1][y]) { a[--x][y] = ++tot; } // 向右走 while(y+1<n && !a[x][y+1]) { a[x][++y] = ++tot; } } // 输出 for(x=0; x<n; x++) { for(y=0; y<n; y++) printf("%3d", a[x][y]); printf("\n"); } return 0; }
字符数组
- 竖式问题
模拟竖式计算，但是必须竖式中所有的字符都必须属于输入的数字集合。#include<stdio.h> #include<string.h> int main() { int count = 0; char s[20], buf[99]; scanf("%s", s); for(int abc=111; abc<=999; abc++) { for(int de=11; de<=99; de++) { int x = abc*(de%10), y = abc*(de/10), z = abc*de; sprintf(buf, "%d%d%d%d%d", abc, de, x, y, z); // 检查每个字符是否都在输入的集合 int ok = 1; for(int i=0; i<strlen(buf); i++) { if(strchr(s, buf[i]) == NULL) ok = 0; } if(ok) { printf("<%d>\n", ++count); printf("%5d\nX%4d\n-----\n%5d\n%4d\n-----\n%5d\n\n", abc, de, x, y, z); } } } printf("The number of solutions = %d\n", count); return 0; } - 趣测试
#include<stdio.h> #include<math.h> int main() { int count = 0; printf("%d %d %d", count++, count++, count++); return 0; }
#include<stdio.h>
int main()
{
int count = 0;
count = count++;
printf("%d", count);
return 0;
}
竞赛题目选讲
- Tex中的引号
getchar，读取下一个字符。#include<stdio.h> int main() { int c, q=1; while((c = getchar()) != EOF) { if(c == '"') { printf("%s", q ? "``":"''"); q = !q; }else{ printf("%c", c); } } return 0; } - WERTUYU
输入一个错位后敲出的字符串，输出打字员本来想打出的句子。输入保证合法。#include<stdio.h> char s[] = "`1234567890-=QWERTYUIOP[]\\ASDFGHJKL;'ZXCVBNM,./"; int main() { int i,c; while((c = getchar()) != EOF) { for(i=1; s[i] && s[i] != c; i++); if(s[i]){ putchar(s[i-1]); }else{ putchar(c); } } return 0; } - 回文词
输入一个字符串，判断它是否为回文串以及镜像串。输入字符串保证不含数字0。所谓回文串，就是反转以后和原串相同，如abba和madam。所有镜像串，就是左右·镜像之后和原串相同，如2S和3AIAE。注意，并不是每个字符在镜像之后都能得到一个合法字符。#include<stdio.h> #include<string.h> #include<ctype.h> // 每个字符的镜像字符 A-Z 1-9 const char* rev = "A 3 HIL JM o 2TUVWXY51SE Z 8 "; // 输出的结果 “不是回文串” “回文串” “镜像串” “镜像回文串” const char* msg[] = {"not a palindrome", "a regular palindrome", "a mirrored string", "a mirrored palindrome"}; char r(char ch) { // isalpha 判断字符是否为字母 if(isalpha(ch)) { return rev[ch - 'A']; } return rev[ch - '0' + 25]; } int main() { char s[30]; while(scanf("%s", s) == 1) { // 字符串长度 int len = strlen(s); // 标志 int p = 1, m = 1; for(int i=0; i<(len+1)/2; i++) { // 是否是回文串 if(s[i] != s[len-1-i]) { p = 0; } // 是否是镜像串 if(r(s[i]) != s[len-1-i]) { m = 0; } } printf("%s -- is %s.\n\n", s, msg[m*2+p]); } return 0; } - 猜数字游戏的提示
实现一个经典“猜数字”游戏。给定答案序列和用户猜的序列，统计有多少数字位置正确（A），有多少数字在两个序列都出现过但位置不对（B）。
这里做了一个小实验，#include<stdio.h> #define maxn 1010 int main() { int n, a[maxn], b[maxn]; int kase = 0; while(scanf("%d", &n) == 1 && n) { printf("Game %d:\n", ++kase); // 输入答案序列 for(int i =0 ; i<n; i++) { scanf("%d", &a[i]); } // 处理猜测序列 for(;;) { int A = 0, B = 0; // 求出位置正确的数字个数A for(int i=0; i<n; i++) { scanf("%d", &b[i]); if(a[i] == b[i]) A++; } // 当猜测序列全为0退出 int sign = 1; for(int i=0; i<n; i++){ if(b[i] != 0){ sign = 0; break; } } if(sign == 1) break; // 找到两个序列都出现过的数字个数B for(int d=1; d<=9; d++) { int c1 = 0, c2 = 0; for(int i = 0; i<n; i++) { if(a[i] == d) c1++; if(b[i] == d) c2++; } if(c1<c2) B += c1; else B += c2; } // 输出结果 printf(" (%d, %d)\n", A, B-A); } } return 0; }#include<stdio.h> #include<math.h> int main() { int count = 0; printf("%d \n", ++count); printf("%d \n", count); return 0; }
再看下面这个程序运行结果，#include<stdio.h> #include<math.h> int main() { int count = 0; printf("%d \n", count++); printf("%d \n", count); return 0; } - 生成元
如果x加上x的各个数字之和得到y，就说x是y的生成元。给出n（1<=n<=100000），
求最小生成元。无解输出0。例如，n=216， 121，2005时的解分别为198，0，1979。// 一次性枚举 #include<stdio.h> #include<string.h> #define maxn 100005 int ans[maxn]; int main() { int T, n; memset(ans, 0, sizeof(ans)); for(int m=1; m < maxn; m++){ int x = m, y = m; // 把x的每一位与x加起来 while(x > 0){ y += x % 10; x /= 10; } // 把最小的生成元保存下来 if(ans[y] == 0 || m < ans[y]){ ans[y] = m; } } scanf("%d", &T); while(T--){ scanf("%d", &n); printf("%d\n", ans[n]); } return 0; } - 环状序列
长度为n的环状串有n种表示法，分别为从某个位置开始顺时针得到。在这些表示法中，字典序最小的称为“最小表示”。
输入一个长度为n（n<=100）的环状DNA串（只包含A、C、G、T这4种字符）的额、一种表示法，你的任务是输出该环状串的最小表示。#include<stdio.h> #include<string.h> #define maxn 105 // 比较分别以p和q为开头的序列 int less(const char* s, int p, int q){ int n = strlen(s); for(int i= 0; i < n; i++){ if(s[(p+i)%n] != s[(q+i)%n]){ return s[(p+i)%n] < s[(q+i)%n]; } } return 0; } int main(){ int T; char s[maxn]; // T个字符串 scanf("%d", &T); // 获取输入、处理字符串 while(T--){ scanf("%s", s); // 到目前为止的标志 int ans = 0; // 字符串的长度 int n = strlen(s); // 找到最小的字符 for(int i=1; i<n; i++){ if(less(s, i, ans)) ans = i; } // 输出最小表示 for(int i=0; i< n; i++){ putchar(s[(i+ans)%n]); } putchar('\n'); } return 0; }
练习
- 得分
给出一个由O和X组成的串（长度为1~80），统计得分。每个O的得分为目前连续出现的O的个数，X的得分为0。#include<stdio.h> #include<string.h> char s[82]; int main() { int score=0; int sign1=0; scanf("%s", s); int strength = strlen(s); for(int i=0; i<strlen(s); i++){ if(s[i] == 'O'){ sign1++; }else{ sign1 = 0; } score += sign1; } printf("%d", score); return 0; } - 分子量
给出一种物质的分子式（不带括号），求分子量。本题中的分子式只包含4种原子，分别为C、H、O、N，原子量分别为12.01，1.008，16.00，14.01（单位：g/mol）。例如，C6H5OH的分子量为94.108g/mol。
记住：字符数字转整形数字的方法#include<stdio.h> #include<ctype.h> #include<string.h> char s[100]; // 每个字母对应的数值 double getNum(char r){ double a = 0.0; if(r == 'C'){ a = 12.01; } if(r == 'H'){ a = 1.008; } if(r == 'O'){ a = 16.00; } if(r == 'N'){ a = 14.01; } return a; } int main(){ scanf("%s", s); double all =0; // 循环遍历 for(int i=0; i< strlen(s); i++){ // 如果是一个字母 if(isalpha(s[i])){ // 如果不是最后一个字符 if(i+1 < strlen(s)){ // 如果下一个是数字 if(!isalpha(s[i+1])){ // 那么相乘 all += getNum(s[i])*(int)(s[i+1]-'0'); continue; }else{ // 不是数字就不用乘 all += getNum(s[i]); continue; } }else{ // 加上最后一个字符 all += getNum(s[i]); continue; } } } printf("%f\n", all); return 0; } - 数数字
把前n（n<=10000）个整数顺次写在一起：123456789101112···数一数0~9各出现多少次，输出10个整数。#include<stdio.h> #include<string.h> int a[10]; char s[100005]; int main() { scanf("%s", s); // 初始化数组 memset(a, 0, sizeof(a)); // 获得输入串的实际长度 int n = strlen(s); // 赋值a数组 for(int i=0; i<n; i++) { int c = (int)(s[i]-'0'); a[c]++; } // 输出数组 for(int i=0; i<10; i++) { printf("%d ",a[i]); } return 0; } - 周期串
如果一个字符串可以由某个长度为k的字符串重复多次得到，则称该串以k为周期。例如，abcabcabcabc以3为周期（注意，它也以6和12为周期）
输入一个长度不超过80的字符串，输出其最小周期。 - 谜题
一个5*5方格，其中恰好有一个格子是空的，其他格子各有一个字母。一共有4种指令：A、B、L、R，分别表示把空格上、下、左、右的相邻字母移到空格中。输入初始网格和指令序列（以数字0结束），输出指令执行完毕后的网格。如有非法指令，应输出“This puzzle has no final configuration.”
上一篇： 动态规划 -- 钢条切割问题
下一篇： 5. C++与STL入门