开灯问题（P39）
n盏灯，编号为1-n，第一个人把所有灯打开，第二个人按下编号为2的倍数的灯的开关，第三个人按下编号为3的倍数的灯的开关，以此类推，一共有k个人，问最后有哪些灯开着。
// 3开灯问题.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <stdio.h>
#include <string.h>
int main(int argc, char* argv[])
{
int n,k;
int a[1005];
int first = 0;
while(scanf("%d%d",&n,&k)){
memset(a,0,sizeof(a));
for(int i=1;i<=k;i++){
for(int j=1;j<=n;j++){
if(j%i==0)a[j] = !a[j];
}
}
for(i=1;i<=n;i++){
if(a[i]){
if(first==0){printf("%d",i);first=1;}
else printf(" %d",i);
}
}
printf("\n");
}
return 0;
}
蛇形填数（P39）
在n*n的方阵里填入1,2,3...，n*n，要求填成蛇形。例如，n=4时的方阵为：
10 11 12 1
9 16 13 2
8 15 14 3
7 6 5 4
先判断，再填数。这个题必须得建立二维数组才输出成这样，所以不要犹豫。
// 3蛇形填数.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <stdio.h>
#include <string.h>
int main(int argc, char* argv[])
{
int n;
int a[10][10];
while(scanf("%d",&n)){
memset(a,0,sizeof(a));
int tot = 0;
int x = 0;
int y = n-1;
a[x][y] = ++tot;
while(tot<n*n){
while(x+1 <= n-1 && a[x+1][y] == 0) a[++x][y] = ++tot;
while(y-1 >= 0 && a[x][y-1] == 0) a[x][--y] = ++tot;
while(x-1 >= 0 && a[x-1][y] == 0) a[--x][y] = ++tot;
while(y+1 <= n-1 && a[x][y+1] == 0) a[x][++y] = ++tot;
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
printf("%3d",a[i][j]);
}
printf("\n");
}
}
return 0;
}
竖式问题（P41）
最开始无从下手，但其实已经遇到很多这样的循环枚举的题目了，就从题意开始，枚举三位数和两位数。
strchr(a,'b')是在字符串a中查找b字符，如果找不到就返回NULL，strlen返回字符串真实长度。
// 3竖式问题.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <stdio.h>
#include <string.h>
int main(int argc, char* argv[])
{
char num[11];
while(scanf("%s",num)){
int count = 1;
for(int i=100;i<1000;i++){
for(int j=10;j<100;j++){
int ok = 1;
int abc = i;
int de = j;
int temp1 = abc * (de%10);
int temp2 = abc * (de/10);
int temp3 = abc * de;
char buf[50];
sprintf(buf,"%d%d%d%d%d",abc,de,temp1,temp2,temp3);
for(int q=0;q<strlen(buf);q++){
if(strchr(num,buf[q])==NULL) ok = 0;
}
if(ok){
printf("<%d>\n",count++);
printf("%5d\nX%4d\n-----\n%5d\n%4d\n-----\n%5d\n",abc,de,temp1,temp2,temp3);
}
}
}
printf("\nThe number of solutions = %d\n",--count);
}
return 0;
}
例题3-1 TeX中的引号（UVa272）（P45）
这个题主要就是知道了
int c;
c = getchar();
是正确的
char c;
c = getchar();
是错误的，因为getchar的返回值是int型。
EOF表示End Of File，表示输入流的结尾，其代表的是-1，用char类型来表示负数是错误的，所以是int。
scanf("%s",s)在读取字符串的时候，遇到空格，Tab，换行都会停止读取。
例题3-2 WERTYU（UVa10082）（P47）
键盘输入右错一位，输入一个错位后的字符串，均大写，输出错位修正后的字符串。
// lt32.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <stdio.h>
#include <string.h>
int main(int argc, char* argv[])
{
char s[] = "`1234567890-=QWERTYUIOP[]\\ASDFGHJKL;'ZXCVBNM,./";
int c;
while((c=getchar())!=EOF){
for(int i=0;i<strlen(s);i++){
if(s[i] == c){putchar(s[i-1]);break;}
}
if(i == strlen(s))putchar(c);
}
printf("\n");
return 0;
}
3-3回文词（UVa401）
判断一个字符串是否是回文串，以及镜像串
// lt33.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#include <ctype.h>
char mirror[] = "A 3 HIL JM O 2TUVWXY51SE Z 8 ";
char fun(char c){
if(isalpha(c))return mirror[c-'A'];
else return mirror[c-'0'+25];
}
int main(int argc, char* argv[])
{
char input[30];
char* msg[] = {"is not a palindrome","is a regular palindrome","is a mirrored string","is a mirrored palindrome"};
char ch[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ123456789";
while(scanf("%s",input)){
int p=1,m=1;
for(int i=0;i<(strlen(input)+1)/2;i++){
//这块不能判断相等然后赋值为1，逻辑会出现错误
if(input[i] != input[strlen(input)-1-i]) p=0;
if(fun(input[i]) != input[strlen(input)-1-i]) m=0;
}
/*
printf("%s -- ",input);
if(m+p==0)printf("%s.\n",msg[0]);
if(m+p==1){
if(m==1) printf("%s.\n",msg[2]);
else printf("%s.\n",msg[1]);
}
if(m+p==2)printf("%s.\n",msg[3]);
*/
printf("%s -- %s.\n.\n",input,msg[2*m+p]);
}
return 0;
}
例题3-4猜数字游戏的提示（UVa 340）
给定答案序列和用户猜的序列，统计有多少数字位置正确（A），有多少数字在两个序列都出现但位置不对（B）
又是一个枚举循环，对于每个数字统计两个序列中数字出现的次数，两个次数取最小值，注意时每个数字都要取最小值然后累加到B上，最后B减A。
// lt34.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <stdio.h>
#define min(a,b) a>b?b:a
int main(int argc, char* argv[])
{
int count;
int num = 1;
while(scanf("%d",&count)&&count){
printf("Game %d:\n",num++);
int a[1005],s[1005];
for(int i=0;i<count;i++){
scanf("%d",s+i);
}
while(1){
int sum=0;
int A=0,B=0;
for(int i=0;i<count;i++){
scanf("%d",a+i);
sum += a[i];
}
if(sum == 0)break;
for(i=0;i<count;i++){
if(a[i] == s[i]) A++;
}
for(i=1;i<=9;i++){
int b1=0,b2=0;
for(int j=0;j<count;j++){
if(a[j] == i)b1++;
if(s[j] == i)b2++;
}
B += min(b1,b2);
}
printf("(%d,%d)\n",A,B-A);
}
}
return 0;
}
例题3-5 生成元（UVa1583）（P52）
如果x加上x的各个数字之和得到y，就说x是y的生成元。给出n（1<=n<=100000），求最小生成元，无解输出零。
第一次做查表的题目。遇到一个数就枚举的话，效率并不高，因为很明显每个数只会对应一个固定的结果，所以完全可以把这些结果都提前计算好，并存储起来，输出结果就直接查表。
// lt35.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <stdio.h>
#include <string.h>
int main(int argc, char* argv[])
{
int ans[100005];
memset(ans,0,sizeof(ans));
for(int i=1;i<=100000;i++){
int x=i,y=i;
while(x>0){
y += x%10;
x = x/10;
}
if(ans[y] == 0 || i < ans[y]) ans[y] = i;
}
int count;
int n;
scanf("%d",&count);
while(count--){
scanf("%d",&n);
printf("%d\n",ans[n]);
}
return 0;
}
例题3-6 环状序列（UVa1584）
最近在网上提交这道题，至少还是参加过比赛的，完全忘记了提交注意事项。
1.因为是用VC写的，
#include "stdafx.h"会有这么一个头，在提交时不要加上。
2.我觉得VC违背了c语言的块级作用域，如图使用会报重复定义的错。但不应该报错的，应该使用其他IDE不会出现这种情况，不得已提出i的定义，放在最开始。点这个网友回答蛮好的
一句话够了，取余来实现循环。
// lt36.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <stdio.h>
#include <string.h>
int less(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 argc, char* argv[])
{
int count;
scanf("%d",&count);
char s[105];
while(count--){
int ans = 0;
int i;
scanf("%s",s);
for(int i=0;i<strlen(s);i++){
if(less(s,i,ans)) ans = i;
}
for(int i=0;i<strlen(s);i++){
putchar(s[(ans+i)%strlen(s)]);
}
printf("\n");
}
return 0;
}
习题3-1 得分(UVa1585)
简单题
#include <stdio.h>
#include <string.h>
int main(int argc, char* argv[])
{
int T;
scanf("%d",&T);
while(T--){
char s[85];
scanf("%s",s);
int tot = 0,sum =0;
for(int i=0;i<strlen(s);i++){
if(s[i] == 'O') {tot++;sum+=tot;}
else tot = 0;
}
printf("%d\n",sum);
}
return 0;
}
习题3-2 分子量(UVa1586)
#include <stdio.h>
#include <string.h>
#include <ctype.h>
int fun(int A,char *str,int i){
if(isdigit(str[i+1])){
if(isdigit(str[i+2])){
A += str[i+2] - '0';
A += (str[i+1] - '0')*10;
}
else
A += str[i+1] - '0';
}
else A++;
return A;
}
int main(int argc, char* argv[])
{
float ch[] = {12.01,1.008,16.00,14.01};
int T;
scanf("%d",&T);
while(T--){
char str[85];
int C=0,H=0,O=0,N=0;
scanf("%s",str);
for(int i=0;i<strlen(str);i++){
if(str[i] == 'C'){
C = fun(C,str,i);
}
else if(str[i] == 'H'){
H = fun(H,str,i);
}
else if(str[i] == 'O'){
O = fun(O,str,i);
}
else if(str[i] == 'N'){
N = fun(N,str,i);
}
}
float sum = ch[0]*C+ch[1]*H+ch[2]*O+ch[3]*N;
printf("%.3f\n",sum);
}
return 0;
}
这个使用传址实现，比较方便，最开始*A没有加括号，导致程序出现错误，所以一定要记得指针在运算时一定要加括号。
#include <stdio.h>
#include <string.h>
#include <ctype.h>
void fun(int *A,char *str,int i){
if(isdigit(str[i+1])){
if(isdigit(str[i+2])){
(*A) += str[i+2] - '0';
(*A) += (str[i+1] - '0')*10;
}
else
(*A) += str[i+1] - '0';
}
else (*A)++;
}
int main(int argc, char* argv[])
{
float ch[] = {12.01,1.008,16.00,14.01};
int T;
scanf("%d",&T);
while(T--){
char str[85];
int C=0,H=0,O=0,N=0;
scanf("%s",str);
for(int i=0;i<strlen(str);i++){
if(str[i] == 'C'){
fun(&C,str,i);
}
else if(str[i] == 'H'){
fun(&H,str,i);
}
else if(str[i] == 'O'){
fun(&O,str,i);
}
else if(str[i] == 'N'){
fun(&N,str,i);
}
}
float sum = ch[0]*C+ch[1]*H+ch[2]*O+ch[3]*N;
printf("%.3f\n",sum);
}
return 0;
}
习题3-3 数数字UVa1225
#include <stdio.h>
#include <string.h>
char s[100000];
int main(int argc, char* argv[])
{
int T;
scanf("%d",&T);
while(T--){
int q[10];
memset(q,0,sizeof(q));
memset(s,'\0',sizeof(s));
int num,i;
scanf("%d",&num);
for(i=1;i<=num;i++){
char buf[10];
sprintf(buf,"%d",i);
strcat(s,buf);
}
for(i=0;i<strlen(s);i++){
q[s[i]-'0']++;
}
for(i=0;i<9;i++){
printf("%d ",q[i]);
}
printf("%d\n",q[9]);
}
return 0;
}
习题3-4 周期串UVa455
像这种类似循环的题目，跟取余一定有关系。原题里的空行我一直没读懂，尴尬英语不好。
#include <stdio.h>
#include <string.h>
int main(int argc, char* argv[])
{
int T;
scanf("%d",&T);
while(T--){
char str[85];
scanf("%s",str);
int length = strlen(str);
for(int i=1;i<=length;i++){
if(length%i == 0){
int j;
for(j=0;j<length;j++){
if(str[j] != str[j%i]) break;
}
if(j == length){
printf("%d\n",i);
break;
}
}
}
if (T) printf("\n");
}
return 0;
}
习题3-5 谜题UVa227
首先解决的是二维数组的输入，考虑到会有空格在输入里，刚开始尝试的是getchar实现，但是要循环读入时，要控制换行\n的读入，存储空格的位置。而且这个题目有坑，就在题目中赋值的测试数据，如果空格在最右边的话，拖拽复制的话根本没有复制到空格，放在控制台直接验证会出错，但依据题意来说，其实是有空格的。
紫书上说gets函数已经被废弃了，但是从这道题发现
#include <stdio.h>
#include <string.h>
#include <ctype.h>
int main(int argc, char* argv[])
{
int count=1;
bool line = false;
while(1){
char init[5][5];
char c;
int puzzle=1;
int i,j;
int bi,bj;
gets(init[0]);
if(init[0][0] == 'Z')return 0;
for(i=1;i<5;i++){
gets(init[i]);
}
for(i=0;i<5;i++){
for(j=0;j<5;j++){
c = init[i][j];
if(c == ' ') {
bi = i;bj = j;
i = 5;j=5;
}
}
}
char command [1000];
bool valid = true;
bool exit_koro = false;
while ( !exit_koro && gets (command)) {
for ( int i = 0; command [i] != 0; i++ ) {
if ( command [i] == '0' || !valid ) {
exit_koro = true;
break;
}
switch (command [i]) {
case 'A' :
if ( bi == 0 )
valid = false;
else {
init [bi] [bj] = init [bi - 1] [bj];
init [bi - 1] [bj] = ' ';
bi--;
}
break;
case 'B' :
if ( bi == 4 )
valid = false;
else {
init [bi] [bj] = init [bi + 1] [bj];
init [bi + 1] [bj] = ' ';
bi++;
}
break;
case 'R' :
if ( bj == 4 )
valid = false;
else {
init [bi] [bj] = init [bi] [bj + 1];
init [bi] [bj + 1] = ' ';
bj++;
}
break;
case 'L' :
if ( bj == 0 )
valid = false;
else {
init [bi] [bj] = init [bi] [bj - 1];
init [bi] [bj - 1] = ' ';
bj--;
}
break;
}
}
}
if ( line )
printf ("\n");
line = true;
printf ("Puzzle #%d:\n", count++);
if ( valid ) {
for ( int i = 0; i < 5; i++ ) {
printf ("%c %c %c %c %c\n", init [i] [0], init [i] [1],
init [i] [2], init [i] [3], init [i] [4]);
}
}
else
printf ("This puzzle has no final configuration.\n");
}
return 0;
}
网友评论