博文
统计数字问题(2009-09-20 19:35:00)
摘要：/*****************************************************************************
算法实现题1-1 统计数字问题
问题描述：
一本书的页码从自然数1 开始顺序编码直到自然数n。书的页码按照通常的习惯编排，
每个页码都不含多余的前导数字0。例如，第6 页用数字6 表示，而不是06 或006 等。数
字计数问题要求对给定书的总页码n，计算出书的全部页码中分别用到多少次数字0，1，
2，…，9。
编程任务：
给定表示书的总页码的10 进制整数n (1≤n≤109) 。编程计算书的全部页码中分别用
到多少次数字0，1，2，…，9。
参考网页：http://blog.csdn.net/jcwKyl/archive/2008/10/02/3009244.aspx
********************************************************************************/
#include <iostream>
#include <vector>
#include <cmath>
#include <iterator>
using namespace std;
int pow(unsigned int idx);
int main()
{
int n; //从1开始编码到n,1<<n<<pow(10,9)
int m; &nb......
动态规划0-1背包问题(2009-08-01 17:41:00)
摘要：#include<iostream>
using namespace std;
//显然定义为全局变量不好
const int item=3;//物品数量
const int max_wgt=10;//背包最大容量
int c[item+1][max_wgt+1];//从1…i…item物品中,背包剩余空间为0<=j<=max_wgt的最大价值
int w[item+1]={0,3,4,5};//物品质量
int vl[item+1]={0,4,5,6}; //物品价值
int knapbag()
{
for (int i=0;i<=item;i++)//初始化
{
for (int j=0;j<=max_wgt;j++)
{
c[i][j]=0;
}
}
//c(i,j)=max{c(i-1,j), c(i-1,j-w[i])+vl(i)}
for (int i=1;i<=item;i++)
{
for (int j=1;j<=max_wgt;j++)
{
if (w[i]<=j)
{
&n......
回溯法N皇后(2009-07-24 15:37:00)
摘要：#include <iostream.h>
#include <math.h>
//x[i] represent to Queen i place in row i group x[i]
void backtrack(int t);
int const n=4;//the number of queen
int x[n+1]; // the solution
int sum=0; //teh number of the solution
int nQueen()
{
for(int i=0;i<=n;i++)
x[i]=0;
backtrack(1);
return sum;
}
bool placesafe(int k)
{
for(int j=1;j<k;j++)
if( abs(k-j)==abs(x[j]-x[k]) || (x[j]==x[k]) )//the slope is 1 or -1,or in the same group
return false;
return true;
}
void backtrack(int t)
{
if(t>n)
{
sum++;
for(int j=1;j<=n;j++)
{
cout<<j<<","<<x[j]<<"#";
}
cout<<endl;
}
else
for( int i=1;i<=n;i++)
{
......
main参数(2008-11-05 09:24:00)
摘要：main参数
C语言中的main函数,一般会带有2个参数,例如int main ( int argc, char* argv[]),这是一个典型的main函数的声明。这是为了在执行程序时需要向程序传递参数,参数argc代表了输入参数的个数,char *argv[]表示传入的参数的字符串,是一个字符串数组。
例如在Unix平台下编写一个小程序:
int main(int argc, char* argv[])
{
int i;
printf("test main parameter\n");
printf("argc:%d\n", argc);
for(i=0;i<argc;i++)
{
printf("argv[%d]:%s\n", i, argv[i]);
}
exit(0);
}
用cc编译后形成一个a.out*的可执行的文件,运行a.out,其结果是argc=1,argv[0]="a.out",运行的程序的文件名,也占用一个参数位置,也就是说argv数组中的第一个单元指向的字符串总是可执行程序的名字,以后的单元指向的字符串依次是程序调用时的参数。这个赋值过程时操作系统完成的,我们只需要拿来用就可以了。
main()主函数
每一C 程序都必须有一main()函数, 可以根据自己的爱好把它放在程序的某
个地方。有些程序员把它放在最前面, 而另一些程序员把它放在最后面, 无论放
在哪个地方, 以下几点说明都是适合的。
1. main() 参数
在Turbo C2.0启动过程中, 传递main()函数三个参数: argc, argv和env。
* argc: 整数, 为传给main()的命令行参数个数。
* argv: 字符串数组。
在......
堆排序和选择排序的效率对比的程序(2006-10-24 12:26:00)
摘要：#include <stdlib.h>
#include <stdio.h>
#include <dos.h>
const int MAXSIZE = 20000;
const int N = 5;
int Data[MAXSIZE];
void Print()
{
int i;
for (i = 0; i < MAXSIZE; i++)
printf ("%d ", Data[i]);
}
void Create()
{
int i;
randomize();
for (i = 0; i < MAXSIZE; i++)
Data[i] = random(1000);
printf("\n");
}
void Swap(int *a, int *b)
{
int temp;
temp = *a;
*a = *b;
*b = temp;
}
void PushDown_MinHeap(int first, int last)
{
long i, j......
2进制的高精度加,减和乘法的C++程序(2006-10-24 12:24:00)
摘要：#include <iostream.h>
#include <mem.h>
const int MAXSIZE = 20; //max length of the number
const int K = 2; //baniry system 在这里可以修改K进制的高精度
class hp{
int len; //length of number
int s[MAXSIZE]; //store high precistion number
public:
hp();
hp hp::operator = (hp C);
};
hp::hp()
{
len = 0;
memset(s, 0, MAXSIZE*sizeof(int));
}
istream &operator >> (istream &in, hp &HP)
{
ch......
二路插入排序 (2006-08-20 12:05:00)
摘要：#include <stdio.h>
#include <stddef.h>
#define ARR_SIZE 10
/* 函数原型 */
void bidir_insert( int keys[], int temp[], const size_t i );
int main(void)
{
size_t i;
int keys[ARR_SIZE] = { 1050, 100, 150, 20, 9000, 5110, 3008, 1450, 5220, 500 };
int temp[ARR_SIZE]; /* 辅助数组 */
/* 进行二路插入排序 */
bidir_insert(keys, temp, ARR_SIZE);
/* 输出排序结果 */
for ( i = 0; i < ARR_SIZE; ++i ) {
printf("%d ", keys[i]);
......
高斯分布随机数源代码(2006-08-20 12:03:00)
摘要：#include <stdlib.h>
#include <math.h>
double gaussrand()
{
static double V1, V2, S;
static int phase = 0;
double X;
if ( phase == 0 ) {
do {
double U1 = (double)rand() / RAND_MAX;
double U2 = (double)rand() / RAND_MAX;
V1 = 2 * U1 - 1;
V......
残缺棋盘（defective chessboard）(2006-08-16 08:58:00)
摘要：残缺棋盘（defective chessboard）是一个有2k×2k 个方格的棋盘，其中恰有一个方格残缺。图2 - 3给出k≤2时各种可能的残缺棋盘，其中残缺的方格用阴影表示。注意当k= 0时，仅存在一种可能的残缺棋盘（如图1 4 - 3 a所示）。事实上，对于任意k，恰好存在22k 种不同的残缺棋盘。
残缺棋盘的问题要求用三格板（t r i o m i n o e s）覆盖残缺棋盘（如图1 4 - 4所示）。在此覆盖中，两个三格板不能重叠，三格板不能覆盖残缺方格，但必须覆盖其他所有的方格。在这种限制条件下，所需要的三格板总数为( 22k -1 ) / 3。可以验证( 22k -1 ) / 3是一个整数。k 为0的残缺棋盘很容易被覆盖，因为它没有非残缺的方格，用于覆盖的三格板的数目为0。当k= 1时，正好存在3个非残缺的方格，并且这三个方格可用图1 4 - 4中的某一方向的三格板来覆盖。
用分而治之方法可以很好地解决残缺棋盘问题。这一方法可将覆盖2k×2k 残缺棋盘的问题转化为覆盖较小残缺棋盘的问题。2k×2k 棋盘一个很自然的划分方法就是将它划分为如图1 4 - 5 a所示的4个2k - 1×2k - 1 棋盘。注意到当完成这种划分后， 4个小棋盘中仅仅有一个棋盘存在残缺方格（因为原来的2k×2k 棋盘仅仅有一个残缺方格）。首先覆盖其中包含残缺方格的2k - 1×2k - 1 残缺棋盘，然后把剩下的3个小棋盘转变为残缺棋盘，为此将一个三格板放在由这3个小棋盘形成的角上，如图14-5b 所示，其中原2k×2k 棋盘中的残缺方格落入左上角的2k - 1×2k&......
1000以内的阶乘(2006-08-14 17:16:00)
摘要：#include<stdio.h>
# include <stdlib.h>
// 计算
# define N 1000
int cal(unsigned int *s,int n)
{
unsigned long p; // p是对每一位乘法中的值加上进位，如34*5,4*5是20,3*5的加上进位2是17
unsigned long k=0; // k是一次乘法中的进位，如10进制乘法中，34*5,4*5的进位是2,3*5的进位是1
int i;
static int m=1; // m是位数，表示s有总共有多少位数字，注意：是1000进制
static int b=0;
/* b用来记录后面的0，比如213,000,000,000，则b=3,后面的3个000不必再参与计算了 */
//
for(i=b;i<m;i++)
{
p=(long)s[i]*(long)n+k;
k=p/N;
s[i]=p-k*N;
}
// b是低位乘出来的000的数目,增加后加1
while(!s[b])
b++;
// 最高位的进位处理
for(k=p/N;k;)
{
p=k;
k=p/N;
s[i++]=p-k*N;
m++; // 进一次m加一次
}
return m;
}&n......