第一章-算法概述

第一题：

问题名称：统计页码数字问题。

问题描述：给定一个数n，计算从0到n出现过多少次0，1，2，...，9。数字n开头不能有0，如6不能表示为06或006。

数据输入：数据输入由input.txt文件提供。每个文件只有1行，给出数字n。

结果输出：将输出结果保存到output.txt文件中。每个文件只有10行，第k行输出数字k-1的次数，k=1，2，...，10。

时间复杂度为O(n * log10(n))的算法：

#include <stdio.h>

void statNumber(int n);

void main()
{
    int n;
    scanf("%d",&n);
    statNumber(n);
}
void statNumber(int n)
{
    int t, i;
    int count[10] = {0};
    
    for(i = 0;i <= n ; i++ ) {
        t = i;
        if( t == 0 ) {
            count[t % 10]++;
        }
        while(t){
            count[t % 10]++;
            t /= 10;
        }
    }
    for(i = 0;i < 10;i++)
        printf("%d
", count[i]);
}

时间复杂度为O(log10(n))的算法：

第二题：

问题名称：最多约数问题。

问题描述：正整数x的约数是能整除x的正整数。正整数x的约数个数记为div(x)。例如，1，2，5，10都是正整数10的约数，且div(10)=4。设a和b是2个正整数，a<=b，找出a和b之间约数个数最多的数x。

数据输入：输入数据由input.txt文件提供，第1行有2个正整数a和b（分开）。

结果输出：程序运行结束时，若找到的a和b之间约数个数最多的数是x，将div(x)输出到output.txt中。

1、求素数：

#include <stdio.h>
#include <math.h>

int isprime(int n);

int main()
{
    int n;
    printf("请输入大于1的正整数：
");
    scanf("%d", &n);
    while (n <= 1)
    {
        printf("请输入大于1的正整数：
");
        scanf("%d", &n);
    }
    printf("%d
", isprime(n));
    return 0;
}

int isprime(int n)
{
    if (n == 2)
        return true;
    if (n % 2 == 0)        //偶数直接排除
        return false;
    for (int i = 3; i <= sqrt(n); i = i + 2)
    {
        if (n % i == 0)
        {
            return 0;
        }
    }
    return 1;
}

2、求一个整型数的位数：

#include <stdio.h>

int main()
{
    int n, i;
    scanf("%d", &n);
    for(i = 0; n != 0; i++)
    {
        n /= 10;
    }
    printf("%d
", i);    //最后i就是位数
    return 0;
}

3、计算两个正整数的最大公约数GCD：

利用欧几里得算法（辗转相除法）：

int GreatestCommonDivisor(int a, int b)
{
    if(b == 0)
        return a;
    else
        return GreatestCommonDivisor(b, a % b);        //粗略的理解就是一直除b，直到能除尽，则b是GCD
}

4、计算n层嵌套平方根：

n层嵌套，就有n个根号，就是有n个sqrt。但是目前的算法到一定的精度，就会不在进位，导致n增大，值不变。

#include <stdio.h>
#include <math.h>

double square(float x, int n)
{
    if (n == 1)
    {
        return sqrt(x);
    }
    else
    {
        return sqrt(x + square(x, n - 1));
    }
}

int main()
{
    double result = square(4, 5000);
    printf("%f
", result);
    return 0;
}

数组转置：

按照原来的顺序输出是：matrix[i][j]，那么转置输出就是：matrix[j][i]。

#include <stdio.h>

#define N 10

void input(int matrix[N][N], int n);
void transpose(int matrix[N][N], int n);
void output(int matrix[N][N], int n);

int main()
{
    int matrix[N][N] = {0};
    int n;
    printf("Input n:
");
    scanf("%d", &n);
    printf("Input %d*%d matrix:
", n, n);
    input(matrix, n);
    printf("The transposed matrix is:
");
    transpose(matrix, n);
    //output(matrix, n);
    return 0;
}
void input(int matrix[N][N], int n)
{
    int i, j;
    for(i = 0; i < n; i++)
    {
        for(j = 0; j < n; j++)
        {
            scanf("%d", &matrix[i][j]);
        }
    }
}
void transpose(int matrix[N][N], int n)
{
    int i, j;
    for(i = 0; i < n; i++)
    {
        for(j = 0; j < n; j++)
        {
            printf("%4d ", matrix[j][i]);
        }
        printf("
");
    }
}
void output(int matrix[N][N], int n)
{
    int i, j;
    for(i = 0; i < n; i++)
    {
        for(j = 0; j < n; j++)
        {
            printf("%d ", matrix[i][j]);
        }
        printf("
");
    }
}