《程序设计》函数题|031-040

习题10-1 判断满足条件的三位数 – 浙大版《C语言程序设计（第4版）》题目集

#include <stdbool.h>
// 返回：是完全平方数->true 否则->false
bool isSquare(int num) {
    if(num<0) return false;
    if (num==0 || num==1) return true;
    long long root = (long long)sqrt(num);
    return (root*root==num) || ((root+1)*(root+1)==num);
}
// 返回：三位数有两位数字相同->true 否则->false
bool isSame2(int num){
    if(num<100 || num>=1000) return false;
    int nums[3];
    for(int i=0;i<3;++i){
        nums[i]=num%10;
        num/=10;
    }
    if(nums[0]!=nums[1]
      && nums[1]!=nums[2]
      && nums[2]!=nums[0]){
        return false;
    }
    return true;
}

// 返回：[101,n]中有两位数字相同的完全平方数个数
int search(int n){
    int cnt=0;
    for(int i=101;i<=n;++i){
        if(isSquare(i) && isSame2(i)){
            ++cnt;
        }
    }
    return cnt;
}

习题10-2 递归求阶乘和 – 浙大版《C语言程序设计（第4版）》题目集

// 递归：求阶乘
double fact(int n){
    // 递归出口
    if(n==0){
        return 1.0;
    }
    // 递归体
    return fact(n-1)*n;
}

// 返回：阶乘和
double factsum(int n){
    // 返回值
    double result=0.0;
    // 求阶乘和
    for(int i=1;i<=n;++i){
        result+=fact(i);
    }
    // 返回
    return result;
}

习题10-3 递归实现指数函数 – 浙大版《C语言程序设计（第4版）》题目集

// 递归：指数函数 
double calc_pow(double x, int n){
    // 递归出口
    if(n==1){
        return x;
    }
    // 递归体
    return calc_pow(x,n-1)*x;
}

习题10-4 递归求简单交错幂级数的部分和 – 浙大版《C语言程序设计（第4版）》题目集

// 返回：求简单交错幂级数的部分和
double fn(double x, int n){
    if(n==1) return x;
    return -pow(-1*x,n)+fn(x,n-1);
}

习题10-5 递归计算Ackermenn函数 – 浙大版《C语言程序设计（第4版）》题目集

// 递归：计算Ackermenn函数
int Ack(int m,int n){
    // 递归出口
    if(m==0){
        return n+1;
    }
    // 递归表达式
    int result;
    if(n==0 && m>0){
        result=Ack(m-1,1);
    }else{
        result=Ack(m-1,Ack(m,n-1));
    }
    return result;
}

习题10-6 递归求Fabonacci数列 – 浙大版《C语言程序设计（第4版）》题目集

// 递归：求Fabonacci数列
int f(int n){
    // 递归出口
    if(n<=1){
        return n;
    }
    // 递归体
    return f(n-1)+f(n-2);
}

习题10-7 十进制转换二进制 – 浙大版《C语言程序设计（第4版）》题目集

// 递归：十进制转换二进制 
void dectobin(int n) {
    // 递归出口
    if(n<2){
        printf("%d",n);
        return;
    }
    // 递归表达式
    dectobin(n/2);
    printf("%d",n%2);
}

习题10-8 递归实现顺序输出整数 – 浙大版《C语言程序设计（第4版）》题目集

// 递归：输出整数
void printdigits(int n){
    if(n<=9){
        printf("%d\n",n);
        return;
    }
    printdigits(n/10);
    printf("%d\n",n%10);    
    return;
}

习题10-11 有序表的增删改查操作 – 浙大版《C语言程序设计（第4版）》题目集

int insert(int a[ ], int value){
    int i, pos;
    
    // 检查value是否已存在
    if (query(a, value) != -1) {
        return -1;
    }
    
    // 找到插入位置
    pos = 0;
    while (pos < Count && a[pos] < value) {
        pos++;
    }
    
    // 将pos及之后的元素后移
    for (i = Count; i > pos; i--) {
        a[i] = a[i-1];
    }
    
    // 插入新元素
    a[pos] = value;
    Count++;
    
    return pos;
}

int del(int a[ ], int value){
    int i, pos;
    
    // 查找value的位置
    pos = query(a, value);
    if (pos == -1) {
        return -1;
    }
    
    // 将pos之后的元素前移
    for (i = pos; i < Count - 1; i++) {
        a[i] = a[i+1];
    }
    
    Count--;
    return pos;
}

int modify(int a[ ], int value1, int value2){
    int pos1, pos2;
    
    // 检查value1是否存在
    pos1 = query(a, value1);
    if (pos1 == -1) {
        return -1;
    }
    
    // 检查value2是否已存在
    if (query(a, value2) != -1) {
        return -1;
    }
    
    // 删除value1
    del(a, value1);
    
    // 插入value2
    insert(a, value2);
    
    return 0;
}

int query(int a[ ], int value){
    int left = 0, right = Count - 1, mid;
    
    while (left <= right) {
        mid = (left + right) / 2;
        if (a[mid] == value) {
            return mid;
        } else if (a[mid] < value) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return -1;
}

练习11-4 字符定位（最后一次找到的字符） – 浙大版《C语言程序设计（第4版）》题目集

// 返回：最后一次找到的该字符在字符串中的位置（地址）
char *match(char *s, char ch){
    char *last_pos = NULL;
    int i = 0;
    
    // 遍历字符串，找到最后一次出现的位置
    while (s[i] != '\0') {
        if (s[i] == ch) {
            last_pos = &s[i];
        }
        i++;
    }
    
    return last_pos;
}