devbox
代码探险家
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

[C] 4. 函数_#include int fac(int n) { int z; if(n>0)

作者：代码探险家 | 2024-07-19 07:32:05

赞

踩

#include int fac(int n) { int z; if(n>0) z=n*fac(n-2); else z=1

目录

1. 基础知识

  • 打印100以内的素数

  1. 函数封装的优点：
    代码可读性好（程序功能逻辑更加直观）、美观性好、调试性好（按函数模块debug）

  2. 写代码的习惯
    ①把不同的功能模块封装成为独立的函数
    ②主函数中只写整个程序开发的架构（功能逻辑的框架），即多个模块之间逻辑上的内容，每个功能逻辑再进行单独封装

  3. C/C++程序执行入口？
    没有特殊情况下（宏），程序执行入口是主函数（main函数）

  4. 函数
    ①返回值类型，无返回值时void
    ②函数名，表述函数功能需求的语义信息，is_prime()是否素数
    ③参数列表，()中的内容：包括参数个数、类型、顺序，作用是将各种类型的值进行传递（传入传出）
    ④函数体
    return向函数调用处返回值，函数体中可以有多个return，但生效的只有1个
    向外传出值的2种方式：return，传出参数（通过指针变量实现，它的功能表现为传出参数）

  5. 函数声明
    ①②③就完成了函数声明
    函数声明的目的是知道怎么使用即可，不需要知道怎么实现，就像我们使用scanf和printf函数一样

  6. 函数定义
    函数声明+函数体就是函数定义

  7. 数学中：y = f(x)
    C语言中：函数传入值，通过功能逻辑返回值，是一种映射；
    数组下标对值也是一种映射；
    故而，函数是压缩的数组，数组是展开的函数，是一种时间换空间的思想。

  8. K&R 风格的函数定义（不建议，因为太老了）
    函数参数的类型声明放在下面

2. 递归

  1. 递归不是算法，是编程技巧，比如for循环+if语句也是编程技巧
    递推是算法，实现递推可以通过循环或者递归
  2. 什么是递归？函数自己调用自己
  3. 递归函数的组成部分
    1. 语义信息：根据需求设计，赋予f(n)含义
    2. 边界条件：递归出口可以有多个，因为无限调用自己就是死循环，所以优先处理递归出口
    3. 递推式子
    4. 结果返回（2种方式：return、传出参数）
  4. 递归的理解：不要纠结于具体是怎么一步一步递与归的，它的本质就是数学归纳法，类似多米诺骨牌

习题2. 计算n的阶乘

#include <stdio.h>

int fac(int n) {
    if (n == 1) return 1;
    return n * fac(n - 1);
}

int main() {
    int n;
    while (scanf("%d", &n) != EOF) {
        printf("fac(%d) = %d\n", n, fac(n));
    }
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  1. factorial阶乘
  2. 怎么验证我们设计的递归函数正确性？
    数学归纳法，fac(1)成立，设fac(k)成立，证fac(k+1)成立，即可证明递推式子没问题
  3. 递归程序经历了2个阶段：向下递推（调用），向上回溯

3. 函数指针

链接：函数指针

  1. 函数的参数列表的功能：将各种类型的值进行传递（传进传出）
    函数指针的功能：把函数当做参数传递

  2. 函数指针
    如果在程序中定义了一个函数，那么在编译时系统就会为这个函数代码分配一段存储空间，这段存储空间的首地址称为这个函数的地址。而且函数名表示的就是这个地址。
    既然是地址我们就可以定义一个指针变量来存放，这个指针变量就叫作函数指针变量，简称函数指针。

  3. 函数指针变量的定义：
    函数返回值类型 (* 指针变量名) (函数参数列表);

  4. 使用传入的函数：直接通过函数名调用，如g函数中直接调用f1函数，return f1(x);

  5. 函数指针的应用：定义分段函数，如上图

欧拉-45 函数指针的应用

在这里插入图片描述

#include<stdio.h>
typedef long long ll;

ll Triangle(ll n) {
    return n * (n + 1) / 2;
}
ll Pentagonal(ll n) {
    return n * (3 * n - 1) / 2;
}
ll Hexagonal(ll n) {
    return n * (2 * n - 1);
}

ll binary_search(ll (*arr)(ll), ll n, ll x) { // 函数指针作为形参
    ll head = 1, tail = n, mid;
    while (head <= tail) {
        mid = (head + tail) >> 1;
        if (arr(mid) == x) return mid; // 调用函数指针
        if (arr(mid) < x) head = mid + 1;
        else tail = mid - 1;
    }
    return -1;
}

int main() {
    ll n = 143; //优化1
    while(1) {
        n += 1;
        ll temp = Hexagonal(n);
        if (binary_search(Pentagonal, temp, temp) == -1) continue;
        //优化2
        //if (binary_search(Triangle, temp, temp) == -1) continue;
        printf("%lld\n", temp);
        break;
    }
    return 0;
}

  • 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
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  1. 二分查找的前提是单调序列，查找数组、函数都可以，本质上需要的是一种映射关系（数组：下标与值，函数：参数与值，都是满足一种映射关系）
  2. 对偶逻辑减少缩进，增加可读性
  3. 如果用int类型（4字节），会陷入死循环
    int类型不足以涵盖下一个所求数，用long long类型（8字节），格式占位符：%lld
  4. 2个优化
    1. 固定六边形数，跨度更大，速度更快，n=143开始
    2. 三角形数包含六边形数：第2n-1个三角形数＝第n个六边形数
  5. 细节
    1. 没必要优化二分的边界temp，因为时间复杂度O(logn)，边界缩小后效果提升不大
    2. 二分查找o(logn)的直观感受，10亿的数查询不超过32次（无符号int型最大值2^32-1≈42亿 > 10亿）
// 基本的二分查找（传数组）
int binary_search(int *arr, int n, int x) { //arr传数组变为(*arr)(int)传函数
    int head = 0, tail = n - 1, mid; //边界head、tail由数组时0~n-1变为函数时1~n
    while (head <= tail) {
        mid = (head + tail) >> 1;
        if (arr[mid] == x) return mid; //arr[mid]对应改为arr(mid)
        if (arr[mid] < x) head = mid + 1;
        else tail = mid - 1;
    }
    return -1;//返回-1不固定，只是表示没有找到x的值
}

int main() {
    ll n = 285;//n==285开始
    while(1) {
        n += 1;
        ll temp = Triangle(n);
        //
        if (binary_search(Pentagonal, temp, temp) != -1) {
            //以当前三角形的值作为项数肯定存在，因为差了一个数量级
            if (binary_search(Hexagonal, temp, temp) != -1) {
                printf("%d\n", temp);
                break;
            }
        }
        //
        //对偶原则减少if嵌套（缩进）:!=变为==，加continue;
        if (binary_search(Pentagonal, temp, temp) == -1) continue;
        if (binary_search(Hexagonal, temp, temp) == -1) continue;
        printf("%lld\n", temp);//%d变为%lld
        break;//退出死循环
    }
    return 0;
}

  • 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
  • 31
  • 32
  • 33
  • 34

4. 欧几里得算法（辗转相除法）

  1. 算法是聪明人的做事方法
  2. 欧几里得算法是已知最古老的算法，体现一种转换思想：安全地从大问题规模转换为小问题规模，并且注意是快速计算
  3. 用于快速计算两个数字的最大公约数
  4. 还可以用于快速求解 a * x + b * y = 1 方程的一组整数解

证明欧几里得算法：gcd(a, b) = gcd(b, a%b)

  1. 设 gcd(a, b) = r,证明 r 是 b, a % b 的公约数
    此时 a = xr, b = yr;
    a % b = a - kb = (x - ky)r，其中 k = floor(a / b)即 k = a / b

  2. 证明 r 是 b, a%b 最大的公约数

    1. 此时 b = yr, a % b = (x - ky)r，要使得 r 最大，需证明 y, x - ky 互素，即 gcd(y, x - ky) = 1
    2. 令 gcd(y, x - ky) = d，证明 d = 1。
      ①此时 y = md, x = ky + nd = (km + n) d
      ②由 gcd(a, b) = r 得 gcd(x, y) = 1（ r 为最大公约数，故 x 与 y 互素），此时 x, y 的公约数 d 只能为1

#include<stdio.h>
int gcd(int a, int b) {
    // if (!b) return a;// b == 0用 !b 表示
    //return gcd(b, a % b);
    return (b ? gcd(b, a % b) : a);//冒号表达式代替上述2行
}
int main() {
    int a, b;
    while(scanf("%d%d", &a, &b)) {//注意没有 != EOF也可以
        printf("gcd(%d, %d) = %d\n", a, b, gcd(a, b));
    }
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13

5. 扩展欧几里得算法

求ax+by=1（a,b,x,y都为整数）的整数解

  • ax+by=1（a,b,x,y都为整数）有整数解，推出gcd(a,b)=1
    设gcd(a, b)=c，则a=cm，b=cn，c(mx+ny)=1
    ∵mx+ny≥1且为整数，∴c=1
  • 特例ax+by=1中b=0，此时x=a=1,y=b=0
    像递归函数f(0)，gcd(1, 0)=1即a=1,b=0时，x=1,y=0(y任意值，赋为0)
  • 假设gcd(b, a%b)=1成立，
[10.ex_gcd.c]

#include <stdio.h>

int ex_gcd(int a, int b, int *x, int *y) {
    if (!b) {
        *x = 1, *y =0;
        return a;
    }
    int xx, yy, ret = ex_gcd(b, a % b, &xx, &yy);
    *x = yy;
    *y = xx - a / b * yy;
    return ret;
}

int main() {
    int a, b, x, y;
    while (scanf("%d%d", &a, &b) != EOF) {
        printf("ex_gcd(%d, %d) = %d\n", a, b, ex_gcd(a, b, &x, &y));
        printf("%d * %d + %d * %d = %d\n", a, x, b, y, a * x + b * y);
    }
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23

6. 变参函数

在这里插入图片描述

#include <stdio.h>
#include <inttypes.h>
#include <stdarg.h>

int max_int(int n, ...) {
    int ans = INT32_MIN;
    va_list arg;
    va_start(arg, n);
    while (n--) {
        int temp = va_arg(arg, int);
        if (temp > ans) ans = temp;
    }
    va_end(arg);
    return ans;
}

int main() {
    printf("%d\n", max_int(3, 1, 5, 10));
    printf("%d\n", max_int(2, 1, 3));
    printf("%d\n", max_int(6, 1, 3, 5, 7, 13, 15, 17)); // 17不比较
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  1. INT32_MIN头文件inttypes.h，va一族头文件stdarg.h
  2. variable argument list 可变参数列表
    1. va_list是类型,定义指针变量arg,保存可变参数(变参)列表的地址
    2. va_start(arg, n); 以最后一个固定参数的地址确定变参的起始地址(变参列表的第一个
    3. va_arg(arg, int); 获取当前参数arg,返回int类型,然后指针执行一次next操作
    4. va_end(arg); 回收指针,避免野指针

7. 实现 my_printf 函数

  1. putchar(‘x’) ：向标准输出（屏幕）打印 1个 字符x
  2. putchar 实现了输出从0到1，printf 实现了输出从1到n
  • 打印字符串hello world
#include <stdio.h>

//const
int my_printf(const char *frm, ...) {
    int cnt = 0;
    for (int i = 0; frm[i]; i++) {//i < strlen(frm)
        putchar(frm[i]), ++cnt;
    }
    return cnt;
}

int main() {
    printf("hello world\n");
    my_printf("hello world\n");
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  1. frm 是格式控制字符串，字符串在C语言中用字符数组进行表示和存储
  2. frm是字符串首地址
  3. 格式控制字符串是字面量，不可以被修改，所以加const
  4. 循环条件 frm[i]，因为系统自动在字符串后面加’\0’
  5. const char *frm 表示 frm 字符串（字符数组）存的值是字面量（常量）
  6. char* const frm 表示 frm 这个指针变量是字面量，即frm这个指针变量不能去记录其他的地址
  • 打印%，123，0
#include <stdio.h>
#include <stdarg.h>

//输出frm后面的变参列表...用变参函数实现
int my_printf(const char *frm, ...) {
    int cnt = 0;
    va_list arg;//定义指针
    va_start(arg, frm);//arg指向frm后面的...的起始地址
    #define PUTC(a) putchar(a), ++cnt
    for (int i = 0; frm[i]; i++) {
        switch (frm[i]) {
            //根据格式控制占位符解读
            case '%': {
                switch (frm[++i]) {
                    case '%': PUTC(frm[i]); break;
                    case 'd': {
                        int x = va_arg(arg, int);//取当前arg位置的int数据
                        int temp = 0;
                        //翻转a（123 -> 321）
                        while (x) {
                            temp = temp * 10 + x % 10;
                            x /= 10;
                        }
                        //打印字符时倒着打印（321 -> '1''2''3'）
                        /*【问题】a == 0时while不打印，do while解决
                        while (temp) {
                            PUTC(temp % 10 + '0');
                            temp /= 10;
                        }*/
                        do {
                            PUTC(temp % 10 + '0');//取temp最后一位的整数，加上'0'或48变成字符对应的ASC码
                            temp /= 10;
                        } while (temp);
                    } break;
                }
            } break;
            default : PUTC(frm[i]); break;
        }
        //PUTC(frm[i]);
        //putchar(frm[i]), ++cnt;封装成一个宏
    }
    #undef PUTC
    return cnt;
}

int main() {
    printf("hello world\n");
    my_printf("hello world\n");
    
    int a = 123;
    my_printf("int (a) = %%\n", a);
    printf("int (a) = %d\n", a);
    my_printf("int (a) = %d\n", a);
    printf("int (a) = %d\n", 0);
    my_printf("int (a) = %d\n", 0);
    return 0;
}

  • 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
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57

声明：本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：【wpsshop博客】
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号