C语言——函数练习

目录

提示：

一、传值调用和传址调用

1.写一个函数能够交换两个整型变量的内容

2.写一个函数可以判断一个数是不是素数。

3.写一个函数，实现一个整形有序数组的二分查找。

4.写一个函数，每调用一次这个函数，就会将 num 的值增加1。

二、函数递归

1.接受一个整型值（无符号），按照顺序打印它的每一位。

2.编写函数不允许创建临时变量，求字符串的长度。

3.求n的阶乘（递归和迭代分别实现）。（不考虑溢出）

4.求第n个斐波那契数。（不考虑溢出）

5.编写一个函数 reverse_string(char * string)（递归实现）

6.写一个递归函数DigitSum(n)，输入一个非负整数，返回组成它的数字之和

7.编写一个函数实现n的k次方，使用递归实现

结束语！

提示：

1）函数功能尽量单一，高内聚，低耦合

2）先写函数怎么用，需要哪些参数，然后再写函数

一、传值调用和传址调用

传址调用是把函数外部创建变量的内存地址传递给函数参数的一种调用函数的方式。

传值调用：函数的形参和实参分别占有不同内存块，对形参的修改不会影响实参。

1.写一个函数能够交换两个整型变量的内容

注：只能用传址调用，如果用传值调用的话不可以，因为形参是实参的一份临时拷贝，对形参的改变不会传递给实参.

void Swap(int* px, int* py)
{
        int z = 0;
        z = *px;
        *px = *py;
        *py = z;
}
int main()
{
        int a = 0, b = 0;
        scanf("%d %d", &a, &b);
        //交换
        printf("%d %dn", a, b);//交换前
        Swap(&a,&b);
        printf("%d %dn", a, b);//交换后
}

2.写一个函数可以判断一个数是不是素数。

普通版：
//打印100-200之间的素数
//素数只能被1和它本身整除的数
#include
int main()
{
        int i = 0;
        int count = 0;
        //除了2之外偶数不可能是素数，所以直接从奇数上找
        for (i = 101; i <= 200; i+=2)
        {
               //判断i是否为素数
               //是素数就打印
               //拿2~i-1之间的数字去试除i
               int flag = 1;//flag是1，表示是素数
               int j = 0;
               //若i不是素数i=a*b，而且a和b中一定有一个数字是<=sart(i)
               //sqrt是数学库函数（开平方），头文件是#include
               for (j = 2; j <= sqrt(i); j++)
               {
                       if (i % j == 0)
                       {
                              flag = 0;
                              break;
                       }
               }
               if (flag == 1)
               {
                       count++;
                       printf("%d ", i);
               }
        }
        printf("n%dn", count);
        return 0;
}

函数版：
//写一个函数判断是不是素数
//是素数返回1，不是素数返回0
int is_prime(int x)
{
        int j = 0;
        for (j = 2; j <= sqrt(x); j++)
        {
               if (x % j == 0)
               {
                       return 0;
               }       
        }
        return 1;
}
int main()
{
        int i = 0;
        int count = 0;
        //除了2之外偶数不可能是素数，所以直接从奇数上找
        for (i = 101; i <= 200; i += 2)
        {
               //判断i是否为素数
               //是素数就打印
               //拿2~i-1之间的数字去试除i
               int flag = 1;//flag是1，表示是素数
               if (is_prime(i))
               {
                       count++;
                       printf("%d ", i);
               }
        }
        printf("n%dn", count);
        return 0;
}

3.写一个函数，实现一个整形有序数组的二分查找。

binary_search()二分查找函数：

//先写函数怎么用，需要哪些参数，然后再写函数
//数组传参实际上传递的是数组首元素地址
//而不是整个数组
//所以在函数内部计算一个函数参数部分的数组的元素个数是不靠谱的
int binary_search(int arr[], int k, int sz)//数组传参不会创建新的数组，只是把首地址传了过去，形参arr看上去是                                               数组，本质上是指针变量
{
        //int sz = sizeof(arr) / sizeof(arr[0]);//arr是指针变量大小是4or8，所以sz=1，
        int left = 0;
        int right = sz - 1;
        while (left <= right)
        {
               int mid = (right - left) / 2 + left;
               if (k > arr[mid])
               {
                       left = mid + 1;
               }
               else if (k < arr[mid])
               {
                       right = mid - 1;
               }
               else
                       return mid;//找到了返回mid
        }
               return -1;//找不到返回-1
}
int main()
{
        int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
        int k = 7;
        int sz = sizeof(arr) / sizeof(arr[0]);
        //找到了的话，返回下标
        //找不到，返回-1
        int ret = binary_search(arr, k, sz);
        if (ret == -1)
        {
               printf("找不到n");
        }
        else
        {
               printf("找到了，下标是:%dn", ret);
        }
        return 0;
}

4.写一个函数，每调用一次这个函数，就会将 num 的值增加1。

void Add(int* p)//传址调用
{
        (*p)++;
}
int main()
{
        int num = 0;
        //调用函数，使得num每次增加1
        Add(&num);
        printf("%dn", num);//1
        Add(&num);
        printf("%dn", num);//2
        Add(&num);
        printf("%dn", num);//3
        Add(&num);
        printf("%dn", num);//4
        return 0;
}

二、函数递归

递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解.

递归策略：只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。

递归的主要思考方式在于：把大事化小

递归存在限制条件，当满足这个限制条件的时候，递归便不再继续。每次递归调用之后越来越接近这个限制条件

1.接受一个整型值（无符号），按照顺序打印它的每一位。

void print(unsigned int n)
{        
    if (n > 9)//如果没有条件会出现死递归，栈溢出，如递归所有控件路径，函数将导致运行时堆栈溢出                               
    {               
        print(n / 10);//123       
    }        
    printf("%d ", n % 10);//4
}

int main()
{        
    unsigned int num = 0;        
    scanf("%d", &num);//1234        
    print(num);//接受一个无符号整型，按照顺序打印它的每一位        
    return 0;
}

//print(1234)
//print(123) 1234%10=4
//print(12)  123%10=3
//print(1)   12%10=2
//1 2 3 4

2.编写函数不允许创建临时变量，求字符串的长度。

#include
//编写函数不允许创建临时变量，求字符串的长度。
//求字符串长度
//模拟实现strlen
//第一个函数实现（没有递归，使用临时变量）
int my_strlen1(char *str)//str现在就是指向a地址
{
        int count = 0;//临时变量，计数
        while(*str != '')
        {
               count++;
               str++;
        }
        return count;
}
//第二个函数（递归，不使用临时变量）
//my_strlen2("abc");
//1+my_strlen2("bc");
//1+my_strlen2("c");
//1+my_strlen2("");
//1+1+1+0
int my_strlen2(char* str)//str现在就是指向a地址
{
        if (*str != '')
        {
               return 1 + my_strlen2(str + 1);//str+1就是b的地址，
        }
        else
        {
               return 0;
        }
        
}
int main()
{
        char arr[] = "abc";
        int len1 = my_strlen1(arr);//函数传字符串是传的首地址
        int len2 = my_strlen2(arr);
        printf("%dn", len1);
        printf("%dn", len2);
        return 0;
}

3.求n的阶乘（递归和迭代分别实现）。（不考虑溢出）

//求n的阶乘。（不考虑溢出）
//递归
int factorial(int n)
{
        if (n <= 1)
               return 1;
        else
               return n * factorial(n - 1);
}

//循环
//迭代实现（非递归）
int factorial(int n)
{
        int i = 0;
        int ret = 1;
        for (i = 1; i <= n; i++)
        {
               ret *= i;
        }
        return ret;
}

int main()
{
        int num = 0;
        scanf("%d", &num);
        int ret = factorial(num);
        printf("%dn", ret);
        return 0;
}

4.求第n个斐波那契数。（不考虑溢出）

斐波那契数列：1  1  2 3 5 8 13 ...

//递归法
int count = 0;
int Fib(int n)
{
        if (n == 3)
               count++;
        if (n <= 2)
        {
               return 1;
        }
        else
               return Fib(n - 1) + Fib(n - 2);
}
//     40
// 39     38
//38 37  37 36
//...................

但是我们发现有问题；

在使用 fib 这个函数的时候如果我们要计算第50个斐波那契数字的时候特别耗费时间。使用 factorial 函数求10000的阶乘（不考虑结果的正确性），程序会崩溃。

那我们如何改进呢？

在调试 factorial 函数的时候，如果你的参数比较大，那就会报错： stack overflow（栈溢出）这样的信息。系统分配给程序的栈空间是有限的，但是如果出现了死循环，或者（死递归），这样有可能导致一直开辟栈空间，最终产生栈空间耗尽的情况，这样的现象我们称为栈溢出

那如何解决上述的问题：

1. 将递归改写成非递归。

2. 使用static（静态）对象替代 nonstatic 局部对象。在递归函数设计中，可以使用 static 对象替代nonstatic 局部对象（即栈对象），这不仅可以减少每次递归调用和返回时产生和释放 nonstatic 对象的开销，而且 static 对象还可以保存递归调用的中间状态，并且可为各个调用层所访问

//非递归法，迭代法
int Fib(int n)
{
        int a = 1;
        int b = 1;
        int c = 1;
        while (n >= 3)
        {
               c = a + b;
               a = b;
               b = c;
               n--;
        }
        return c;
}
int main()
{
        int n = 0;
        scanf("%d", &n);
        int ret = Fib(n);
        printf("%dn", ret);
        //printf("%dn", count);
        return 0;
}

注：

1. 许多问题是以递归的形式进行解释的，这只是因为它比非递归的形式更为清晰。

2. 但是这些问题的迭代实现往往比递归实现效率更高，虽然代码的可读性稍微差些。

3. 当一个问题相当复杂，难以用迭代实现时，此时递归实现的简洁性便可以补偿它所带来的运行时开销。

5.编写一个函数 reverse_string(char * string)（递归实现）

//实现：将参数字符串中的字符反向排列，不是逆序打印。

//要求：不能使用C函数库中的字符串操作函数。

//char arr[] = "abcdef";

//逆序之后数组的内容变成：fedcba

//char arr[] = "abcdef";
//逆序之后数组的内容变成：fedcba
#include
#include
//非递归法

void my_reverse_string(char* arr)
{
      char* left = arr;
      char* right = arr + strlen(arr) - 1;
      
      while (left < right)
      {
             char tmp = *left;
            *left = *right;
            *right = tmp;

             left++;
             right--;
      }
}

//法二：递归法
/*
递归方式：
对于字符串“abcdefg”，递归实现的大概原理：
  1. 交换a和g，
  2. 以递归的方式逆置源字符串的剩余部分，剩余部分可以看成一个有效的字符串，再以类似的方式逆置
  比如字符串“abcdef”先拿出a，将g放在a的位置，g的位置补0，
  即“fbcde”指针向后偏移，指向下一个字符串“bcde”依次类推，直到下一个字符串长度为1时不再执行递归操作。
  
  int MyStrlen(char* str)
{
        int count = 0;
        while (*str != '')
        {
               count++;
               str++;
        }
        return count;
}
void reverse(char *str)
{
        char tmp = *str;//1
        int len = MyStrlen(str);
        *str = *(str + len - 1);//2
        *(str + len - 1) = '';//3
        if(MyStrlen(str+1)>=2)
               reverse(str + 1);//4
        *(str + len - 1) = tmp;//5
}
int main()
{
        char arr[] = "abcdefg";
        reverse(arr);
        printf("%sn", arr);
        return 0;
}

//法三：设置参数
void reverse(char arr[], int left, int right)
{
        char tmp = arr[left];
        arr[left] = arr[right];
        arr[right] = tmp;
        if (left < right)
               reverse(arr, left + 1, right - 1);
}
int main()
{
        char arr[] = "abcdefg";
        int left = 0;
        int right = strlen(arr) - 1;
        reverse(arr, left, right);
        printf("%sn", arr);
        return 0;
}

6.写一个递归函数DigitSum(n)，输入一个非负整数，返回组成它的数字之和

//例如，调用DigitSum(1729)，则应该返回1 + 7 + 2 + 9，它的和是19
//输入：1729，输出：19
int DigitSum(int n)
{
        if (n >= 10)
        {
               return n % 10 + DigitSum(n / 10);
        }
        return n;
}
int main()
{
        unsigned int n = 0;
        scanf("%u", &n);
        int sum = DigitSum(n);
        printf("%dn", sum);
        return 0;
}

7.编写一个函数实现n的k次方，使用递归实现

//k有正有负
//power(n,k)=n*power(n,k-1);
//power(n,k-1)=n*power(n,k-2);
// .......
// power(n,2)=n*power(n,1);
//k=4  n
//3    n*n
//2    n*n*n
//1    n*n*n*n
#include
double power(int n, int m)
{
        if(m > 0)
        {
               return n * power(n, m - 1);//不可以用m--，
        }
        else if (m == 0)
        {
               return 1;
        }
        else
               return 1.0/ power(n, -m);
}
int main()
{
        int num = 0;
        int k = 0;
        scanf("%d %d", &num, &k);
        double ret = power(num, k);
        printf("%lfn", ret);
        return 0;
}

结束语！

关于函数递归这一块儿，是我在学习函数的时候感觉很难的地方，所以总结了一些典型例题发出来，分享一些心得，也希望得到大家的建议。