ChihHuCheYeh's Blog

C 典型题与一些基础算法

2018/09/04 Share

这里主要是集合了一些典型的基础练习与考试题目,均是自己整理所得,主要是备用。或许会有一些小瑕疵,随时更新….
有些题是来自谭书,没办法,考试嘛,只能这样了。

数字处理

加减乘除/交换选择

输入一个三位数,分别输出其每位的数字。

1
2
3
4
5
6
7
8
9
10
11
12
#include <stdio.h>
int main()
{
int num;
int x,y,z;
scanf("%d",&num);
x=num%10; //个位
y=num/10%10; //十位
z=num/100; //百位
printf("%d,%d,%d",x,y,z);
return 0;
}

取个位:num%10

取十位:num/10%10

取百位:num/100%10 …

即是 当前数字 / 位数 % 10

注意,这个方法仅是冰山一角。

获取一串整数的长度:

1
2
3
4
5
6
7
8
9
10
11
12
#include <stdio.h>
int main()
{
int num=23;
int count=0;
while(num!=0)
{
num/=10;
count++;
}
return 0;
}

输入两个数字于变量x和y,将x和y的值交换后输出。

1
2
3
4
5
6
7
8
9
10
11
12
#include <stdio.h>
int main()
{
int x,y;
int temp; //中转变量
scanf("%d%d",&x,&y);
temp=x;
x=y;
y=temp;
printf("x:%d,y:%d\n",x,y);
return 0;
}

指针传参方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>
void swap(int *x,int *y);
int main()
{
int x,y;
scanf("%d%d",&x,&y);
swap(&x,&y);
printf("x:%d,y:%d\n",x,y);
return 0;
}
void swap(int *x,int *y)
{
int temp;
temp=*x;
*x=*y;
*y=temp;
}

求1至100的累加总和。

1
2
3
4
5
6
7
8
9
10
11
#include <stdio.h>
int main()
{
int i;
int sum;
sum=0;
for(i=1;i<=100;i++)
sum+=i;
printf("%d",sum);
return 0;
}

求1至20的阶乘乘积。

1
2
3
4
5
6
7
8
9
10
#include <stdio.h>
int main()
{
int i;
double sum=1.0;
for(i=1;i<=20;i++)
sum*=i;
printf("%.1f",sum);
return 0;
}

由于阶乘的乘积大小是不可预估的,int型变量可能无法完整的装下乘积,故此可以使用double/float或longlong类型来装载乘积。

求所有的水仙花数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <stdio.h>						
int main()
{
int n;
int x,y,z;
for(n=100;n<1000;n++)
{
x=n%10; //个位
y=n/10%10; //十位
z=n/100; //百位
if(x*x*x+y*y*y+z*z*z==n)
printf("%4d",n);
}
return 0;
}

水仙花数是个 3 位数,它的每个位上的数字的 3次幂之和等于它本身,所以每次循环都要提取当前循环变量的各个位,随后使它们的三次幂相加和与n比较,如果相等,即是水仙花数。

数组/矩阵

输入一系列数字,找出其中最大/最小的数字

最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>
#define N 5
int main()
{
int list[N];
int i,max;
for(i=0;i<N;i++)
scanf("%d",&list[i]);
max=list[0];
for(i=1;i<N;i++)
{
if(max<list[i])
max=list[i];
}
printf("max=%d\n",max);
return 0;
}

最小值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>
#define N 5
int main()
{
int list[N];
int i,min;
for(i=0;i<N;i++)
scanf("%d",&list[i]);
min=list[0];
for(i=1;i<N;i++)
{
if(min>list[i])
min=list[i];
}
printf("max=%d\n",min);
return 0;
}

输入若干数字,将它们从小到大/从大到小排序后输出。

冒泡排序法:重复访问本数组,每次访问时将相邻的两个元素进行比较,如果规律错误(指是否是从大到小或是从小到大),则会对它们进行互换,直到本数组没有再发生互换动作,即完成了排序。

  1. 比较相邻的元素。如果第一个比第二个大/小,就交换他们两个。
  2. 对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大/小的数。
  3. 针对所有的元素重复以上的步骤,除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

从小到大

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#define N 5
int main()
{
int list[N];
int i,j;
int temp;
for(i=0;i<N;i++)
scanf("%d",&list[i]);
for(i=0;i<N-1;i++) //n-1=N-1次
for(j=0;j<N-i-1;j++) //此处的n-1=(N-i)-1
if(list[j]>list[j+1])
{
temp=list[j];
list[j]=list[j+1];
list[j+1]=temp;
}
for(i=0;i<N;i++)
printf("%d\t",list[i]);
return 0;
}

从大到小

将上述程序 if(list[j]>list[j+1]) 处改为 if(list[j]<list[j+1])

改进后的冒泡排序

以一个flag变量标志为是否继续进行交换和访问的条件,初始值置为1,如果发生了交换,flag的值会在交换后置为0,继而不满足后方脱出循环的if条件,继续进行交换,如果确实已经交换完毕,那么flag的值会仍然为1,即满足了if(flag)的条件,脱出循环,提高了效率,不必在排序完后仍然继续访问,做无用功。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int flag;				//标志 
for(i=0;i<N;i++)
{
flag=1;
for(i=0;i<N-1;i++)
for(j=0;j<N-i-1;j++)
if(list[j]>list[j+1])
{
temp=list[j];
list[j]=list[j+1];
list[j+1]=temp;
flag=0; //发生了交换,继续在下一轮循环中排序。
}
if(flag) //是否又发生了交换,如果没发生表示排序完毕,退出循环。
break;
}

###具有下列一个3 x 3 大小的数字矩阵,分别求出它主对角线与次对角线之和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <stdio.h>
#define N 3
int main()
{
int array[N][N]=
{
{1,2,4},
{6,9,7},
{8,3,1}
};
int s1,s2;
int i,j;
s1=0,s2=0;
for(i=0;i<N;i++)
for(j=0;j<N;j++)
{
if(i==j)
s1+=array[i][j];
else if(i+j==2)
s2+=array[i][j];
}
printf("s1:%d\ns2:%d\n",s1,s2);
return 0;
}

主对角线s1:位于主对角线上的两个元素的下标均是[0][0]与[2][2],之所以,当i=j的时,此时所访问到的元素即是主对角线中的两个元素,将它们相加即可得出主对角线中元素的和。
次对角线s2:位于次对角线上的两个元素是[0][2]与[2][0],当i+j=2时,此时所访问到的元素必定是次对角线中的两个元素,将它们相加即可得出次对角线中元素的和。

将此4 x 3大小的数字矩阵进行转置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <stdio.h>
#define R 3 //行
#define C 4 //列
int main()
{
int array_a[R][C]=
{
{1,2,4,7},
{6,9,7,9},
{8,3,1,2}
};
int array_b[C][R]; //将行与列互换
int i,j;
for(i=0;i<R;i++)
for(j=0;j<C;j++)
array_b[j][i]=array_a[i][j]; //转置
for(i=0;i<C;i++)
{
printf("\n");
for(j=0;j<R;j++)
printf("%4d\t",array_b[i][j]);
}
return 0;
}

所谓矩阵转置,就是将原矩阵的行变成列,列变成行,形成一个3 x 4 的矩阵,准备一个array_b数组存放转制后array_a的元素,array_b也是一个二维数组,如果array_a的行列是[3][4],则array_b的行列是[4][3]。
将array_a的i行j列元素赋值给array_b的j行i列元素,就实现了转置,也不会出现越界现象。

找出此3 x 3矩阵中最大的数,然后输出它本身以及所在行列信息。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <stdio.h>
#define R 3
#define C 3
int main()
{
int array[R][C]=
{
{1,2,4},
{6,9,7},
{8,3,1}
};
int max;
int row,col; //行、列信息
int i,j;
row=0,col=0;
max=array[0][0]; //假定最大值
for(i=0;i<R;i++)
for(j=0;j<C;j++)
{
if(max<array[i][j])
{
max=array[i][j];
row=i; //记录行信息
col=j; //记录列信息

}
}
printf("\tmax:%d\n\tpostion(%d,%d)\n",max,row,col);
return 0;
}

使用row与col记录行与列的信息,max来存放最大值,首先假定整个数组中第一个元素[0][0]为最大的一个数字,随后使他逐个与数组中的其它元素进行比较,如果发现了比自己还大的数字,就将最大的数字赋值给自己,与此同时使用将此刻i与j的值赋给row与col,这样就完成了位置的记录,随后多次循环,一直循环到末尾,即可找到最大值与它所在的行列位置。

反之寻找最小值即是将条件换作if(max>array[i][j])即可。

简单图形

输出一个具有7行高度的直角三角形。

1
2
3
4
5
6
7
8
9
10
11
12
#include <stdio.h>
int main()
{
int i,j;
for(i=1;i<=7;i++)
{
for(j=0;j<i;j++)
printf("*");
printf("\n");
}
return 0;
}

以外层循环变量i确定总行数(高),内层循环变量j确定每行的列数,以这种方式,每行输出j=i列 * ,即是一个具有7行高度的倒三角形。
本程序也可以逆向输出一个倒的直角三角形。

1
2
3
4
5
6
for(i=7;i>=1;i--)
{
for(j=0;j<i;j++)
printf("*");
printf("\n");
}

仅需要改变外层循环的架构,让它第一行就输出7列 * ,逐次递减,即可构成一个倒的直角三角形。

输出一个具有5行高度的等腰三角形。

1
2
3
4
5
6
7
8
9
int i,j,k;
for(i=1;i<=5;i++)
{
for(k=0;k<7-i-1;k++)
printf(" ");
for(j=0;j<2*i-1;j++)
printf("*");
printf("\n");
}

i与j依旧控制高度和列,k则控制了三角形是否等腰,所谓等腰三角形既是在屏幕的每一行中输出相应的空格后再输出*所构成的。

输出一个菱形:即是先输出一个正的等腰三角,随后改变外层循环变量值再逆序输出。

字符处理

在ASCII中 , A~Z的值为65~90,a~z的值为97~122,0~9的值为48~57。

大写字母与小写字母之间的差值为32,小写字母的值>大写字母的值。

如果要推算一个字母的值,可以使用它的起始值往后数,以此类推。

字符

输入一个字母字符,如果字母是大写就转换为小写,如果是小写就转换为大写。

1
2
3
4
5
6
7
8
9
10
11
12
#include <stdio.h>
int main()
{
char ch;
ch=getchar();
if(ch>='A'&&ch<='Z')
ch+=32;
if(ch>='a'&&ch<='z')
ch-=32;
printf("%c",ch);
return 0;
}

连续输入一串字符,大小写互相转换,其余字符保持不变,输入以字符‘!’结束。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <stdio.h>
int main()
{
char ch;
while((ch=getchar())!='!')
{
if(ch>='A'&&ch<='Z')
ch+=32;
if(ch>='a'&&ch<='z')
ch-=32;
putchar(ch);
}
return 0;
}

字符串

strcpy函数的手动实现。

1
2
3
4
5
6
7
8
9
10
void mystrcpy(char *str1,char *str2)
{
int i;
i=0;
while(str2[i]!='\0')
{
str1[i]=str2[i];
i++;
}
}

strcat函数的手动实现。

1
2
3
4
5
6
7
8
9
10
11
void mystrcat(char *str1,char *str2)
{
int i;
int j;
i=j=0;
while(str1[i]!='\0') //定位str1的末尾位置
i++;
while(str2[j]!='\0')
str1[i++]=str2[j++]; //str2的值从str1的末尾陆续追加
str1[i]='\0'; //str1末尾补'\0'
}

strlen函数的手动实现。

1
2
3
4
5
6
7
8
int mystrlen(char* str)
{
int i;
i=0;
while(*(str+i)!='\0')
i++;
return i;
}
CATALOG
  1. 1. 数字处理
    1. 1.1. 加减乘除/交换选择
      1. 1.1.1. 输入一个三位数,分别输出其每位的数字。
      2. 1.1.2. 获取一串整数的长度:
      3. 1.1.3. 输入两个数字于变量x和y,将x和y的值交换后输出。
        1. 1.1.3.1. 指针传参方式
      4. 1.1.4. 求1至100的累加总和。
      5. 1.1.5. 求1至20的阶乘乘积。
      6. 1.1.6. 求所有的水仙花数。
    2. 1.2. 数组/矩阵
      1. 1.2.1. 输入一系列数字,找出其中最大/最小的数字
        1. 1.2.1.1. 最大值
        2. 1.2.1.2. 最小值
      2. 1.2.2. 输入若干数字,将它们从小到大/从大到小排序后输出。
        1. 1.2.2.1. 从小到大
        2. 1.2.2.2. 从大到小
        3. 1.2.2.3. 改进后的冒泡排序
      3. 1.2.3. 将此4 x 3大小的数字矩阵进行转置。
      4. 1.2.4. 找出此3 x 3矩阵中最大的数,然后输出它本身以及所在行列信息。
    3. 1.3. 简单图形
      1. 1.3.1. 输出一个具有7行高度的直角三角形。
        1. 1.3.1.1. 输出一个具有5行高度的等腰三角形。
  2. 2. 字符处理
    1. 2.1. 字符
      1. 2.1.1. 输入一个字母字符,如果字母是大写就转换为小写,如果是小写就转换为大写。
      2. 2.1.2. 连续输入一串字符,大小写互相转换,其余字符保持不变,输入以字符‘!’结束。
    2. 2.2. 字符串
      1. 2.2.1. strcpy函数的手动实现。
      2. 2.2.2. strcat函数的手动实现。
      3. 2.2.3. strlen函数的手动实现。