一些C/C++的算法小程序

1,打印ASCII字符：#include<iostream> #include<iomanip> using namespace std;class table { public:table(int p):i(p) {} void ascii(); protected:int i; }; void table::ascii() { ...

diaoqu4574

125人浏览 · 2019-10-06 12:56:32

diaoqu4574 · 2019-10-06 12:56:32 发布

1,打印ASCII字符：

#include<iostream>
#include<iomanip>
using namespace std;

class table
{
public:
    table(int p):i(p) {}
    void ascii();
protected:
    int i;
};

void table::ascii()
{
    int k = 1;
    for (; i <= 128; i++)
    {
        cout<<setw(4)<<i<<' '<<(char)i;
        if (!(k%12))
            cout<<endl;
        k++;
    }
    cout<<endl;
}

void main()
{
    table tbl1(1);
    tbl1.ascii();
    cout<<endl;

    table tbl2('a');
    tbl2.ascii();
}

n的阶乘(n!)末尾零(0)的个数快速估算方法

一般来说，随着数值n的增大，n的阶乘末尾的零越来越多，而末尾零的个数是可以通过n精确计算出来的，但通常情况下，这种计算过于复杂，本文提供一种可以快速估算n!末尾零个数的方法，使用起来十分简便，而且误差也很小。

例如：30!=265252859812191058636308480000000

数一下，其末尾有7个零。

再如：100!= 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

数一下，其末尾有24个零。

于是我们要问，那么n!的末尾有多少个零呢？

答案：可以用(n-1)/4并取整来估算（或干脆直接用n/4来估算）。

如上面30!末尾有(30-1)/4=7个零，而100!末尾则有(100-1)/4=24个零。

可以设想：先求出100!的值，然后数一下末尾有多少个零。事实上，与上题一样，由于计算机所能表示的整数范围有限，这是不可能的。
　　为了解决这个问题，必须首先从数学上分析在100!结果值的末尾产生零的条件。不难看出：一个整数若含有一个因子5，则必然会在求100!时产生一个零。因此问题转化为求1到100这100个整数中包含了多少个因子5。若整数N能被25整除，则N包含2个因子5；若整数N能被5整除，则N包含1个因子5。
*程序说明与注释
#include<stdio.h>
int main()
{
int a,count =0;
for(a=5;a<=100;a+=5) //循环从5开始，以5的倍数为步长，考察整数
{
++count; //若为5的倍数，计数器加1
if(!(a%25)) ++count; //若为25的倍数，计数器再加1
}
printf("The number of 0 in the end of 100! is: %d./n",count); //打印结果
return 0;
}

*运行结果
The number of 0 in the end of 100! is: 24.

*问题进一步讨论

本题的求解程序是正确的，但是存在明显的缺点。程序中判断整数N包含多少个因子5的方法是与程序中的100有关的，若题目中的100改为1000，则就要修改程序中求因子5的数目的算法了。

3.如何快速找出一个8bits数中的1的个数，要求算法效率尽量高！

#include
#define BYTE unsigned char
/* 定义查找表 */
BYTE numTable[256] =
{
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3,
3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3,
4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4,
3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3,
4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6,
6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4,
5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3,
4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4,
4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6,
7, 6, 7, 7, 8
};
int main(int argc, char *argv[])
{
int i, num = 0;
BYTE a = 0;
/* 接收用户输入 */
printf("/nPlease Input a BYTE(0~255):");
scanf("%d", &a);
/* 计算1 的个数 */
/* 用BYTE 直接作为数组的下标取出1 的个数，妙哉！ */
printf("/nthe num of 1 in the BYTE is %d", checknum[a]);
return 0;
}

int main()
{
    int x;
    cin>>x;
    if(x>255)
    {
        cout<<"error!"<<endl;
        return -1;
    }
    int cnt = 0;
    if((x&128) == 128)
        cnt++;
    if((x&64) == 64)
        cnt++;
    if((x&32) == 32)
        cnt++;
    if((x&16) == 16)
        cnt++;
    if((x&8) == 8)
        cnt++;
    if((x&4) == 4)
        cnt++;
    if((x&2) == 2)
        cnt++;
    if((x&1) == 1)
        cnt++;
    cout<<cnt<<endl;
    return 0;
};