这里是笔者在PTA上面做题的一些整理和总结，这些都是很基础的题目，做完之后偶有自己的想法和总结，故把它们记录下来，梳理一下，其中包含部分题目，附有详细的代码实现。
这里是对PTA上基础习题的一个总结
5-2.本题要求实现一个函数，计算N个整数中所有奇数的和，同时实现一个判断奇偶性的函数。
int even( int n );
int OddSum( int List[], int N );
实现过程:
int even( int n )
{
if(n%2==0) return 1;
else return 0;
}
int OddSum( int List[], int N )
{
int sum=0;
for(int i=0;i<N;++i)
{
if(even(List[i])==0) sum+=List[i];
}
return sum;
}
涉及到负数的时候，奇数的判定就有了一点问题，余数可能是-1；
所以，余数为0就是偶数，余数非零就是奇数
5.4.本题要求实现一个判断素数的简单函数、以及利用该函数计算给定区间内素数和的函数。
素数就是只能被1和自身整除的正整数。注意：1不是素数，2是素数。
int prime( int p );
int PrimeSum( int m, int n );
其中函数prime当用户传入参数p为素数时返回1，否则返回0；函数PrimeSum返回区间[m, n]内所有素数的和。题目保证用户传入的参数m≤n。
实现过程：
int prime( int p )
{
if(p<2) return 0;
for(int j=2;j*j<=p;++j)
if(p%j==0) {return 0;break;}
return 1;
}
int PrimeSum( int m, int n )
{
if(n<2) return 0;
if(m<0) m=2;
int sum=0;
for(int i=m;i<=n;++i)
{
if(prime(i)) sum+=i;
}
return sum;
}
这种算法，时间复杂度为log(N*N);实际并不可取
5.5.本题要求实现一个统计整数中指定数字的个数的简单函数。
int CountDigit( int number, int digit );
其中number是不超过长整型的整数，digit为[0, 9]区间内的整数。函数CountDigit应返回number中digit出现的次数。
实现过程：
int CountDigit( int number, int digit )
{
if(number==0)
{
if(digit==0) return 1;
else return 0;
}
if(number<0) number=-number;
int j,s=0;
while(number!=0)
{
if(number%10==digit) ++s;
number=number/10;
}
return s;
}
这里我的操作是，先将负数转化为正数，零单独讨论，最后只考虑整数的情况，利用while循环，依次求出每个数位上的数字，在这个过程中同时进行判断和计数即可.
5.6.水仙花数是指一个N位正整数（N≥3），它的每个位上的数字的N次幂之和等于它本身。例如：153;
本题要求编写两个函数，一个判断给定整数是否水仙花数，另一个按从小到大的顺序打印出给定区间(m,n)内所有的水仙花数。
int narcissistic( int number );
void PrintN( int m, int n );
实现过程：
#include<math.h>
int narcissistic( int number )
{
char a[10000];
int backnum=number;
int i=0,sum=0;
while(number!=0)
{
a[i]=number%10;
number=number/10;
++i;
}
for(int j=0;j<i;++j)
sum+=pow(a[j],i);
if(sum==backnum) return 1;
else return 0;
}
void PrintN( int m, int n )
{
for(int i=m+1;i<n;++i)
{
if(narcissistic(i)) printf("%d\n",i);
}
}
思路：先申请一个数组，然后备份原来的数字，通过while循环，找到每一位的数字并记录，最后，求和与之前备份的原数字比较并得出结论,毕竟一开始并不知道有几位数字。其中数组用的比较大（捂脸）。
5.7.本题要求实现一个函数，用下列公式求cos(x)的近似值，精确到最后一项的绝对值小于e：
double funcos( double e, double x );
其中用户传入的参数为误差上限e和自变量x；函数funcos应返回用给定公式计算出来、并且满足误差要求的cos(x)的近似值。输入输出均在双精度范围内。
实现过程：
double funcos( double e, double x )
{
double sum=1,pre,cha;
double i=0,h=1;
//for(i=2;fabs(h)>e;i+=2)
while(fabs(h)>=e)
{
h=h*x*(-1)*x/(i+1)/(i+2);
sum+=h;
i=i+2;
}
return sum;
}
思路：将增加的那一项表示出来
只是一个int和double的问题，让我纠结了半天，一定要重视这种类型，别写错。另：注意sum的实际含义，别想当然，模拟几组数，一定要一步一步的清晰的写出来
6.1.本题要求实现一个函数，统计给定字符串中英文字母、空格或回车、数字字符和其他字符的个数。
void StringCount( char s[] );
实现过程：
#include<string.h>
void StringCount( char s[] )
{
int let=0,deg=0,oth=0,blank=0;
for(int i=0;i<strlen(s);++i)
{
if((s[i]>='a'&&s[i]<='z')||(s[i]>='A'&&s[i]<='Z'))
++let;
else if(s[i]>='0'&&s[i]<='9')
++deg;
else if(s[i]==' '||s[i]=='\n')
++blank;
else ++oth;
}
printf("letter = %d, blank = %d, digit = %d, other = %d",let,blank,deg,oth);
}
类似这种统计的问题，直接一次循环遍历，期间进行判断和计数即可，值得注意的是，不用知道具体的ASCII码，直接对字符进行比较即可
6.2.给定两个均不超过9的正整数a和n，要求编写函数求a+aa+aaa++⋯+aa⋯a（n个a）之和。
int fn( int a, int n );
int SumA( int a, int n );
实现过程：
int fn( int a, int n )
{
int m=0;
for(int i=1;i<=n;++i)
m=m*10+a;
return m;
}
int SumA( int a, int n )
{
int sum=0;
for(int i=1;i<=n;++i)
sum+=fn(a,i);
return sum;
}
实现思路：如果给定一个一位数字a，利用for循环控制次数，然后每次的操作都是a=a*10+a；最后就会变成aaaa；至于第二个求和函数，在第一问的基础上就很简单了.(微笑)
6.3.本题要求实现一个计算整数因子和的简单函数，并利用其实现另一个函数，输出两正整数m和n（0<m≤n≤10000）之间的所有完数。所谓完数就是该数恰好等于除自身外的因子之和。例如：6=1+2+3，其中1、2、3为6的因子。
int factorsum( int number );
void PrintPN( int m, int n );
其中函数factorsum须返回int number的因子和；函数PrintPN要逐行输出给定范围[m, n]内每个完数的因子累加形式的分解式，每个完数占一行，格式为“完数 = 因子1 + 因子2 + ... + 因子k”，其中完数和因子均按递增顺序给出。如果给定区间内没有完数，则输出一行“No perfect number”。
实现过程：
int factorsum( int number )
{
if(number==1) return 1;//这里有个很严重的问题，题目出错，毕竟，1的本身就是1，那么“除掉本身”怎么理解呢？故而1的算法与主算法不同
else
{int sum=0;
for(int i=1;i<number;++i) //遍历，判断并计数；
{
if(number%i==0) sum+=i;
}
return sum;}
}
void PrintPN( int m, int n )
{ int count=0;//用来记录完数的个数，如果最后count为0，则应打印"No perfect number"
if(m==1) {printf("1 = 1\n");m=m+1;++count;}//1的独特算法，单独讨论
for(int i=m;i<=n;++i)
{
if(factorsum(i)==i) //判断是不是完数，如果是的话，执行打印操作；不是掠过
{
printf("%d = 1",i);
++count;
for(int j=2;j<i;++j)
{
if(i%j==0) printf(" + %d",j);
}
printf("\n");
}
}
if(count==0) printf("No perfect number");
}
注意等号与赋值号不要弄混，要不然总会有奇奇怪怪的问题出现；本题思路还是挺清晰的，主要在于1的迷惑性
6.4.本题要求实现一个计算Fibonacci数的简单函数，并利用其实现另一个函数，输出两正整数m和n（0<m≤n≤10000）之间的所有Fibonacci数。所谓Fibonacci数列就是满足任一项数字是前两项的和（最开始两项均定义为1）的数列。
int fib( int n );
void PrintFN( int m, int n );
其中函数fib须返回第n项Fibonacci数；函数PrintFN要在一行中输出给定范围[m, n]内的所有Fibonacci数，相邻数字间有一个空格，行末不得有多余空格。如果给定区间内没有Fibonacci数，则输出一行“No Fibonacci number”。
int fib( int n )
{
if(n==1||n==2) return 1;
return fib(n-1)+fib(n-2);
}
void PrintFN( int m, int n )
{
int i=1;
int count=0;
while(fib(i)<=n)
{
if(fib(i)>=m)
{++count;//利用count去计数，第一个
if(count==1) printf("%d",fib(i));
else printf(" %d",fib(i));}
++i;
}
if(count==0) printf("No Fibonacci number");
}
此题比较基础，与之前的题目大有重复
6.5.本题要求实现一个判断素数的简单函数，并利用该函数验证哥德巴赫猜想：任何一个不小于6的偶数均可表示为两个奇素数之和。素数就是只能被1和自身整除的正整数。注意：1不是素数，2是素数。
int prime( int p );
void Goldbach( int n );
其中函数prime当用户传入参数p为素数时返回1，否则返回0；函数Goldbach按照格式“n=p+q”输出n的素数分解，其中p≤q均为素数。又因为这样的分解不唯一（例如24可以分解为5+19，还可以分解为7+17），要求必须输出所有解中p最小的解。
实现过程：
int prime( int p )
{
if(p==1) return 0;
else
{for(int i=2;i*i<=p;++i)
{
if(p%i!=0) continue;
else return 0;
}
return 1;
}
}
void Goldbach( int n )
{
for(int i=1;i<n-1;++i)
{
if(!prime(i)) continue;//直到遇到第一个数字为素数，进入下一个语句
if(prime(n-i)) {printf("%d=%d+%d",n,i,n-i);break;}//一定不要忘记括号，特别是if语句的作用域
}
}
第一个实现判断素数的算法，直接对每一个不大于sqrt（n）的数字去验证能否整除n，如果不能整除，（符合素数的定义），利用continue一直继续，直到i可以整除n；n是合数，返回值为0；
而第二个函数本质上是判断两个数字都是素数，只有在第一个是素数的条件下判断第二个，还是利用了continue语句。
函数二另解：
void Goldbach( int n ){
int a;
int count=0;
for(a=2; a<=n;a++){
if(prime(a)==1&&prime(n-a)==1){
count++;
if(count==1){
printf("%d=%d+%d",n,a,n-a);
}
}
}
}
6.6.本题要求实现一个求整数的逆序数的简单函数。
int reverse( int number );
其中函数reverse须返回用户传入的整型number的逆序数。
实现过程：
int reverse( int number )
{
int flag=1,sum=0,t;//flag用来标记负数，这里sum=0不仅是初始化，还照顾到了number=0的情况
if(number<0) {flag=-1;number=-number;}
while(number>0)
{
t=number%10;//典型
number=number/10;
sum=sum*10+t;
}
return sum*flag;
}
8.8.本题要求编写函数，将输入字符串的前3个字符移到最后。
void Shift( char s[] );
其中char s[]是用户传入的字符串，题目保证其长度不小于3；函数Shift须将按照要求变换后的字符串仍然存在s[]里。
实现过程：
void Shift( char s[] )
{
char t[3];
int q=strlen(s);
t[0]=s[0];
t[1]=s[1];
t[2]=s[2];
for(int i=0;i<q-3;++i)
s[i]=s[i+3];
s[q-3]=t[0];
s[q-2]=t[1];
s[q-1]=t[2];//直接就是最基本的交换，🆗
}
基本思路就是先将前三个字符备份，然后s[i]=s[i+3];最后再将后三个字符更改即可，想法很简单；
8.3.本题要求实现一个对数组进行循环右移的简单函数：一个数组a中存有n（>0）个整数，将每个整数循环向右移m（≥0）个位置，即将a中的数据由(a0a1 ⋯a(n−1))变换为(a(n−m)⋯a(n−1)a0a1⋯a(n−m−1))（最后m个数循环移至最前面的m个位置）。
int ArrayShift( int a[], int n, int m );
其中a[]是用户传入的数组；n是数组的大小；m是右移的位数。函数ArrayShift须将循环右移后的数组仍然存在a[]中。
实现过程：
int ArrayShift(int a[],int n,int m)
{
m=m%n;
int cop[n];//做个备份，当然也不需要全部备份，只需备份一部分，这里为了省事😀
for(int i=0;i<n;++i)
cop[i]=a[i];
for(int i=n-1;i>=m;--i)
a[i]=a[i-m];//核心
for(int i=0;i<=m-1;++i)
a[i]=cop[n-m+i];
}
这里有一个问题，如果我申请另外一个数组，所有的操作都是对新数组而言，最后将新数组赋值给所要求的数组，就会出错(emmmmm).
8.5.本题要求编写函数，将输入字符串t中从第m个字符开始的全部字符复制到字符串s中。
void strmcpy( char *t, int m, char *s );
函数strmcpy将输入字符串char *t中从第m个字符开始的全部字符复制到字符串char *s中。若m超过输入字符串的长度，则结果字符串应为空串。
实现过程：
#include<string.h>
void strmcpy( char *t, int m, char *s )
{
int len=strlen(t);
if(m>len) { s='\0';}
else
{
for(int i=(m-1);i<len;++i)
s[i-(m-1)]=t[i];}//是将t的那些字符转移到s中，而这些字符串在s中是从头开始的
}
将语言叙述转换成逻辑顺序就行，没有什么难度。
8.6.本题要求实现一个删除字符串中的指定字符的简单函数。
void delchar( char *str, char c );
其中char *str是传入的字符串，c是待删除的字符。函数delchar的功能是将字符串str中出现的所有c字符删除。
实现过程：
#include<string.h>//暴力解决，以最大的代价解决它
void delchar( char *str, char c )
{
int len=strlen(str),j=0;
for(int i=0;i<len;++i)
{
if(str[i]==c)
{
for(j=i;j<len-1;++j)
{
str[j]=str[j+1];
}
str[len-1]='\0';
len=len-1;
i=i-1;//这一行代码解决了一个问题，只要碰到了c，i就不再自增1；怎么处理？i-=1;(笑哭)
}
}
}
另解：
void delchar( char *str, char c )
{
int i,j,t=1;
for(i=MAXN-1;i>=0;i--)
{
if(str[i]==c)
{
for(j=i;j<MAXN-t;j++)
{
str[j]=str[j+1];
}
t++;
}
}
}
对于从一个序列中删除某个字符，数组的时间复杂度O(N),而如果采用链表结构，则为O(1);
实现思路是利用for循环依次遍历，每当遇到指定要删除的字符时，对它和它之后的每个字符操作，全体向前移动一位，最后空出来的一位赋值'\0',数组长度减小1；如此反复进行，可实现将所有的指定字符删除，过程较为繁琐。
8.8.本题要求编写函数，判断给定的一串字符是否为“回文”。所谓“回文”是指顺读和倒读都一样的字符串。如“XYZYX”和“xyzzyx”都是回文。
bool palindrome( char *s );
函数palindrome判断输入字符串char *s是否为回文。若是则返回true，否则返回false。
实现过程：
#include<string.h>
bool palindrome( char *s )
{
int len=strlen(s);
for(int i=0;i<=len/2;++i)
{
if(s[i]==s[len-i-1]) continue;
else return false;
}
return true;
}
思路就是从数组的头尾向中间进攻，依次判断对应位置的值是否相等
10.7本题要求实现一个函数，将正整数n转换为二进制后输出。
void dectobin( int n );
函数dectobin应在一行中打印出二进制的n。建议用递归实现。
实现过程：
void dectobin( int n ) {
if ( n / 2 > 0 )
dectobin( n / 2 );
printf("%d", n % 2);
}
递归真的很巧妙，对栈的调用与这种思想，真的很巧妙
10.8.本题要求实现一个函数，对一个整数进行按位顺序输出。
void printdigits( int n );
函数printdigits应将n的每一位数字从高位到低位顺序打印出来，每位数字占一行。
实现过程：
void printdigits( int n ){
if(n<10)//出口
{
printf("%d\n",n);//123456-12345-1234-123-12-1，然后1->1，12%10->2，123%10->3...输出1，2，3，4，5，6
}else{
printdigits(n/10);
printf("%d\n",n%10);// 这样的顺序,当输入123456,出来 1 2 3 4 5 6,说明123456/10 一直整除到6
//如果交换 123456 输出 6 5 4 3 2 1
}
}
巧妙！
11.2.本题要求实现函数，可以根据下表查找到星期，返回对应的序号。
| 序号 | 星期 |
|---|---|
| 0 | Sunday |
| 1 | Monday |
| 2 | Tuesday |
| 3 | Wednesday |
| 4 | Thursday |
| 5 | Friday |
| 6 | Saturday |
int getindex( char *s );
函数getindex应返回字符串s序号。如果传入的参数s不是一个代表星期的字符串，则返回-1。
实现过程：
int getindex(char *s)
{
int week;
char *day[7] = { "Sunday","Monday","Tuesday","Wednesday","Thursday","Friday","Saturday" };
for (week = 0; week <= 6; week++){
if (strcmp(s, day[week]) ==0) break;
}
if (week == 7) week = -1;
return week;
}
这道题目中值得注意的问题是，switch case语句中switch的使用范围
any expression of integral or enumeration type, or of a class type contextually implicitly convertible to an integral or enumeration type, or a declaration of a single non-array variable of such type with a brace-or-equals initializer.
整数或枚举类型的任何表达式，或上下文隐式可转换为整数或枚举类型的类类型的任何表达式，或使用大括号或等于初始化器声明的该类型的单个非数组变量。
也就是： switch 后面括号内的“表达式”必须是整数类型。也就是说可以是 int 型变量、char 型变量，也可以直接是整数或字符常量，哪怕是负数都可以。但绝对不可以是实数，float 型变量、double 型变量、小数常量通通不行，全部都是语法错误。
11.5.本题要求实现一个函数，对给定的一个字符串和两个字符，打印出给定字符串中从与第一个字符匹配的位置开始到与第二个字符匹配的位置之间的所有字符。
char *match( char *s, char ch1, char ch2 );
函数match应打印s中从ch1到ch2之间的所有字符，并且返回ch1的地址。
实现过程：
char *match( char *s, char ch1, char ch2 ) //仔细想想为什么没有写出来
{
int i=0;
char *rtn;
for(;(i<strlen(s))&&(s[i]!=ch1);i++);
rtn=&s[i];
for(;i<strlen(s);i++)
{
printf("%c",s[i]);
if(s[i]==ch2)
break;
}
printf("\n");
return rtn;
}
11.6.本题要求实现一个字符串查找的简单函数。
char *search( char *s, char *t );
函数search在字符串s中查找子串t，返回子串t在s中的首地址。若未找到，则返回NULL。
#include <string.h>
char *search(char *s, char *t){
char *p=NULL;
int i,j,k=0,lens,lent;
lens = strlen(s);
lent = strlen(t);
for(i=0;i<lens;i++){
j=i;
while(s[j]==t[k]){
k++;
j++;
}
if(k>=lent){ // k>=lent 才能满足 长度超过题面MAXS, t在结尾处 这个条件
p=&s[i];
return p;
}
k=0;
}
return p;
}
8.4.本题要求编写函数，给出每个人的退出顺序编号。
报数游戏是这样的：有n个人围成一圈，按顺序从1到n编好号。从第一个人开始报数，报到m(<n)的人退出圈子；下一个人从1开始报数，报到m的人退出圈子。如此下去，直到留下最后一个人。
void CountOff( int n, int m, int out[] );
其中n是初始人数；m是游戏规定的退出位次（保证为小于n的正整数）。函数CountOff将每个人的退出顺序编号存在数组out[]中。因为C语言数组下标是从0开始的，所以第i个位置上的人是第out[i-1]个退出的。
实现过程：
void CountOff( int n, int m, int out[] )
{
int book[MAXN]={0};
int i=0;//i是用来记录位置的，判断每次循环是对哪个位置进行的
int count=0,p=0,j=0;//p是步数，每次走路的步数，从而判断是否已经排除
while(count<n)//count是用来判断多少人出队的
{
if(book[i]!=-1)
++p;
if(p==m)
{
++j;
out[i]=j;
p=0;
book[i]=-1;
++count;
}
++i;
if(i==n) i=0;
}
}
