发现onepixel作者的一篇解释经典算法挺好的文章：https://www.cnblogs.com/onepixel/articles/7674659.html

素数

质数（prime number）又称素数，有无限个。质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数，这样的数称为质数。

#include <stdio.h>
 
int checkPrimeNumber(int n);
int main()
{
    int n1, n2, i, flag;
 
    printf("输入两个正整数: ");
    scanf("%d %d", &n1, &n2);
    printf("%d 和 %d 间的素数为: ", n1, n2);
 
    for(i=n1+1; i<n2; ++i)
    {
        // 判断是否为素数
        flag = checkPrimeNumber(i);
 
        if(flag == 1)
            printf("%d ",i);
    }
    return 0;
}
 
// 函数定义
int checkPrimeNumber(int n)
{
    int j, flag = 1;
 
    for(j=2; j <= n/2; ++j)
    {
        if (n%j == 0)
        {
            flag =0;
            break;
        }
    }
    return flag;
}

可以考虑用sqrt降低时间复杂度

#include<stdio.h>
#include<math.h>
int issushu(int k);
int main(){
    int n,count=0;
    scanf("%d",&n);
    for(int i=n;i>3;i--)
        if(issushu(i))
            if(issushu(i-2))
                count++;
    printf("%d",count);
    return 0;
}

int issushu(int k){
    for(int i=2;i<sqrt(k)+1;i++){
        if(k%i==0)
        return 0;
    }
    return 1;
}

水仙花数

在数论中，水仙花数用来描述一个N位非负整数，其各位数字的N次方和等于该数本身
例：

153 = 13 + 53 + 33。
370 = 33 + 73 + 03。
371 = 33 + 73 + 13。
407 = 43 + 03 + 73。

解法1：

#include<stdio.h>
int main()
{
    int i,j,k;
    for(i=1;i<=9;i++)
        for(j=0;j<=9;j++)
            for(k=0;k<=9;k++)
            if(k*k*k+j*j*j+i*i*i==i*100+j*10+k)
            printf("%d\n",i*100+j*10+k);
        getchar();
}

解法2：

#include<stdio.h>
#define bai (num/100)
#define shi  ((num-bai*100)/10)
#define ge  (num%10)
int main()
{
    int num;
    for(num=100;num<1000;num++)
    if(num==bai*bai*bai+shi*shi*shi+ge*ge*ge)
    printf("%d\n",num);
 
    retutn 0;
}

斐波那契数列

斐波那契数列指的是这样一个数列 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，2584，4181，6765，10946，17711，28657，46368........

这个数列从第3项开始，每一项都等于前两项之和。

输出指定数字前的斐波那契数列
#include <stdio.h>
 
int main()
{
    int t1 = 0, t2 = 1, nextTerm = 0, n;
 
    printf("输入一个正数: ");
    scanf("%d", &n);
 
    // 显示前两项
    printf("斐波那契数列: %d, %d, ", t1, t2);
 
    nextTerm = t1 + t2;
 
    while(nextTerm <= n)
    {
        printf("%d, ",nextTerm);
        t1 = t2;
        t2 = nextTerm;
        nextTerm = t1 + t2;
    }
    
    return 0;
}

快速排序

版本1：

void quiksort(int a[],int low,int high)
{
    int i = low;
    int j = high;  
    int temp = a[i]; 
  
    if( low > high)
    {          
       return ;
    }
    while(i < j) 
        {
            while((a[j] >= temp) && (i < j))
            { 
                j--; 
            }
            a[i] = a[j];
            while((a[i] <= temp) && (i < j))
            {
                i++; 
            }  
            a[j]= a[i];
        }
     a[i] = temp;
     quiksort(a,low,i-1);
     quiksort(a,j+1,high);
}

版本2：

void quick_sort(int s[],int l,int r)
{
    if(l < r)
    {
        int i=l,j=r,x=s[l];
        while(i<j)
        {
            while(i<j && s[j]>=x)//从右到左找到第一个小于x的数  
                j--;
            if(i<j)
                s[i++]=s[j];
            
            while(i<j && s[i]<=x)//从左往右找到第一个大于x的数  
                i++;
            if(i<j)
                s[j--]=s[i]; 
            
        }
        
        s[i]=x;//i = j的时候，将x填入中间位置  
        quick_sort(s,l,i-1);//递归调用 
        quick_sort(s,i+1,r);        
    }
}

冒泡排序

版本1：

//一般实现
void bubble_sort(int a[],int n)//n为数组a的元素个数
{
    //一定进行N-1轮比较
    for(int i=0; i<n-1; i++)
    {
        //每一轮比较前n-1-i个，即已排序好的最后i个不用比较
        for(int j=0; j<n-1-i; j++)
        {
            if(a[j] > a[j+1])
            {
                int temp = a[j];
                a[j] = a[j+1];
                a[j+1]=temp;
            }
        }
    }

版本2：

//优化实现
void bubble_sort_better(int a[],int n)//n为数组a的元素个数
{
    //最多进行N-1轮比较
    for(int i=0; i<n-1; i++)
    {
        bool isSorted = true;
        //每一轮比较前n-1-i个，即已排序好的最后i个不用比较
        for(int j=0; j<n-1-i; j++)
        {
            if(a[j] > a[j+1])
            {
                isSorted = false;
                int temp = a[j];
                a[j] = a[j+1];
                a[j+1]=temp;
            }
        }
        if(isSorted) break; //如果没有发生交换，说明数组已经排序好了
    }
}

本文由 weti 创作，采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Mar 25, 2019 at 10:40 pm