博文
马踏棋盘的贪心算法(2005-08-25 12:20:00)
摘要：我的作业，凑合一篇吧……
C语言课程设计实验报告
马踏棋盘的贪心算法
123041-23 XX
【问题描述】
马的遍历问题。在８×８方格的棋盘上，从任意指定方格出发，为马寻找一条走遍棋盘每一格并且只经过一次的一条路径。
【初步设计】
首先这是一个搜索问题，运用深度优先搜索进行求解。算法如下：
１、 输入初始位置坐标x,y；
２、 步骤 c:
如果c>64输出一个解，返回上一步骤c--
(x,y) ← c
计算(x,y)的八个方位的子结点，选出那此可行的子结点
循环遍历所有可行子结点，步骤c++重复2
显然（２）是一个递归调用的过程，大致如下：
void dfs(int x,int y,int count)
{
int i,tx,ty;
if(count>N*N)
{
output_solution();//输入一个解
return;
}
for(I=0;i<8;++i)
{
tx=hn[i].x;//hn[]保存八个方位子结点
ty=hn[i].y;
s[tx][ty]=count;
dfs(tx,ty,count+1);//递归调用
s[tx][ty]=0;
}
}
这样做是完全可行的，它输入的是全部解，但是马遍历当８×８时解是非常之多的，用天文......
产生任意范围内的等概率随机数(2005-08-17 21:34:00)
摘要：C提供的标准随机函数是rand()，返回0~RAND_MAX，共RAND_MAX+1个随机数，如果我需要更大的随机数范围应如何做？
试设计：
long random(long n);返回0~n-1间的等概率随机数
分情况讨论
如果n<RAND_MAX+1，大可以用rand()%n的方法做，但这样做也并不能满足等概率性，设r=RAND_MAX%n，得到0~r的概率要稍大一些，尤其在n较接近RAND_MAX时，当n较小时影响可以忽略。
if(n<=RAND_MAX)
{
r=RAND_MAX-(RAND_MAX+1)%n;//尾数
t=rand();
while(t>r)t=rand();
return t%n;
}
如果n>=RAND_MAX+1，我的想法是分段抽样，分成[n/(RNAD_MAX+1)]段，先等概率得到段再得到每段内的某个元素，这样分段也类似地有一个尾数问题，不是每次都刚好分到整数段，一定或多或少有一个余数段，这部分的值如何选取？
选到余数段的数据拿出来选取，先进行一次选到余数段概率的事件发生，然后进行单独选取：
else
{
r=n%(RAND_MAX+1);//余数
if(happened((double)r/n))//选到余数段的概率
return n-r+ra......
称小球问题的数学证明(2005-08-16 23:29:00)
摘要：[转自CSDN]由网友feng5166(枫之羽)间接提供
【问题描述】
十三个球看上去一模一样，但其中一个质量不同（不知道是重了还是轻了），现在有一个天平，要求给出一种操作的方法，使得在不超过三次之内把这个球找出来（排除一切偶然情况），给出必胜策略。
【推广到N个小球】
有N个小球外形无区别，但是有一个在质量上与其他的球不一样。用天平称最少m次一定将不同的球找出来。显然随N增大，m不会减小。现在想解决的问题是对于任何给定的次数m,找出在该次数下能解决的最大的N值,用Nmax来表示。并给出对应于(Nmax,m)的一种解法。
【关于所能解决的上限】
现在来求m次所能解决的上限Nmax(m)问题。
为解决这个问题，我们给出几个引理。
引理一：无论加上什么其他的附加条件，只要k个球中的任一个都有可能是坏球（概率不
为0），则当k>3^L时，称L次是称不出来的。这里的附加条件包括已知坏球是否重于好球,
除k个未知球外还提供若干个标准球，以及k个球中某些的质量和大于另外一些的和等等，
只要在这些条件下k个球中的任一个都还有可能是坏球就可以是引理所说的附加条件。
证明：很显然，若k>3^L，则哪个球是坏球一共有k中情况，而称L次一共有3^L种情况，
由k>3^L知不可能一定分辨出哪个球是坏球。
引理二：如果另外在提供任意多个标准球（即在N个未知球外还任给标准球作"砝码"用）?br /> 则称m次最多能从N1max(m)=(3^m+1)/2个球中找出坏球来。
证明：对该引理的证明可以采用数学归纳法。
当m=1时，显然若只有两个球，则任挑一个与另外的标准球比较（额外提供的，不是
两个中的），若相等则是剩下那一个，若不等则是这一个。所以N1max(1)>=2。
而对于三个球的情况，如果第一次称用了两个或三个未知球，则无法判断出用
过的球中谁是坏球（只称一次），而如果第一次称只用了一个未知球，则剩下
的两个球无法区分。因此一次不能解决三个球的问题。所以N1max(1)<3。
由N1max(1)<3和N1max(1)>=2知，N1max=2。
设当m<=k-1时命题都成立，则考虑m=k的情况。
第一次称不能使用超过3^(k-1)个未知球，否则如果坏球在这超过3^(k-1)个
球中的话，由引理一，在剩下的(k......
满足任意精度的概率事件发生器(2005-08-16 21:40:00)
摘要：#include<iostream.h>
#include<time.h>
#include<stdlib.h>
#define MinProb 3.05185094759972e-5
bool happened(double probability)//probability 0~1
{
if(probability<0)return false;
if(probability<MinProb)
return rand()==0&&happened(probability/MinProb);
if(rand()<=probability*RAND_MAX)
return true;
return false;
}
MinProb是理论上的最小发生概率，为什么会这样，因为计算机是离散的，它永远只能得到有限范围内的随机离散数。
bool happened(double probability);
是按概率probability发生的随机事件发生器，如当probability=0.5时，将等概率得到真或者假，当为其它值时，将按probability的概率得到真，以1-probability的概率得到假。
如果probability比较大，MinProb是足够精确的，如0.5和0.5000001是有足够精确相等的，它相当于一个大概率加一个小概率，小概率被‘吃’掉了。
而小概率事件单独发生能不能突破MinProb的极限呢？
我昨天睡觉的时候想出来了这样的算法，从理论上是可以无限精确的，即任意小的小概率事件都可以得到。
其实原理非常简单，即独立事件同时发生的概率等于各事件的概率之积。举个例子：
void main()
{
long happen=0;
&nb......
[TOJ]1072输出你自己的代码(2005-08-15 17:35:00)
摘要：输出你自己的代码
Time Limit:1s Memory Limit:1000k Special Judge
Total Submit:3800 Accepted:1174
--------------------------------------------------------------------------------
Problem
你曾经看到过这样的程序吗？当它运行的时候，将会输出一些字符，这些字符恰好组成了这个程序的代码本身。
请你写这样的一个程序。
请注意，你的程序运行时将不能访问到源程序（系统已经将源代码删除）。
Input
本题没有输入数据。
Output
输出必须和你提交的代码本身一致。
那个回车弄得我好晕，不过后来还是成功了！
#include<stdio.h>
int main(){char *s;printf("#include<stdio.h>\n");printf(s,34,92,34,34,s="int main(){char *s;printf(%c#include<stdio.h>%cn%c);printf(s,34,92,34,34,s=%c%s%c,34);return 0;}",34);return 0;}......
分酒问题-搜索解法(2005-08-15 02:54:00)
摘要：//分酒
/*有四个人喝酒，有两个八两装满酒的瓶，
只有一个三两的杯子。他们要平分这些酒，
但是不能借用其它的工具，你觉得应该怎么做？
*/
#include<iostream.h>
int position[6354][8];//状态集
long ptop=0;
//后来实验的结果是，在求解的过程中可能出现6354种状态
int object[7]={8,8,0,0,0,0,0};//0,1瓶,2杯,3~6人，写在一起只是为了便于搜索
int solution[60][3];//保存解过程：a,b,n a->b(n)
int cmin=100;//最少步数
int scount=0;
int pour(int a,int b)
//从a编号对象往b编号对象转移时，反回可行转移的酒量,返回0表示非法
{
int empty;
if(object[a]==0)return 0;
if(a==b)return 0;
//if(a>2)return 0;//不能从人往容器转移
if(b<3)//容器往容器
{
empty=b<2?8-object[b]:3-object[b];
if(object[a]<empty)return object[a];
return empty;
}
else//容器往人
{
empty=4-ob......
高考作文-Diablo版(2005-08-12 00:49:00)
摘要：
游戏背景：一个年轻人，在漫漫人生路上经历过长途跋涉，到达一个渡口的时候，他身上已经有了七个背囊：是美貌、金钱、荣誉、诚信、机敏、健康、才学。渡船开出的时候风平浪静，过了不知道多久，风起浪涌，上下颠簸，险象环生。老艄工对年轻人说：“船小，负载重，客官你必须丢掉一个背囊，才可安全到达。”看年轻人不肯丢掉任何一个，老艄工又说：“有弃有取，有失有得。”年轻人想了想，把“诚信”丢到水里。因此，有了此篇作文。
最近我狂玩Diablo 2毁灭之王，比原来的游戏新加了两个角色：刺客和战士，这样“大菠”就有了七种角色：男巫、女巫、骑士、亚马逊MM、野蛮人、战士、刺客。
上面的故事正好有七个背囊，在创建游戏角色时我制定出一个最佳配置方案：把“美貌”分给女巫，这样让她更容易迷惑敌人；把“金钱”分给骑士，好让他可以在五星级客栈里安顿要护送的妞，不必像赵匡胤送京娘一样风餐露宿有伤MM身体；把“才学”分给男巫，可以帮助他把法术练到顶级；把“诚信”分给刺客——这是中国的优良传统，看看《刺客列传》就明白了；把“机敏”给勇猛的亚马逊MM，让她们手中的箭和投枪能射中更远的敌人；把“荣誉”分战士，他一定会衣锦还乡；最后把“健康”分给野蛮人。
在这个游戏中，我只扮演野蛮人。我的人生因此非常简单，当然你也可以说成是单调。在战士眼里，一切都无所谓。除了健康，我不需要其他任何一种元素。
于是，在整个旷野里，我是一名孤独的战士，拒绝和别的玩家结成同盟，拒绝学习最基本的法术。我顶着沉重的盔甲，挥舞着血迹斑斑的锈斧在人烟罕至的荒野里默默砍杀，无数次我独自抛尸荒野，这没什么，轮回之后我依然在荒野时砍杀任何一个我遇到的人类。
最后——
女巫被我的惊世丑陋吓疯了，她发出的闪电巧妙地击中了自己的天灵盖；
男巫的法术让我死了N+1回，最后我仅仅用斧子就生生把他劈成了两半；
骑士早已被酒色掏空了身子，很easy就一斧拦腰劈断了他以及他后面的妞；
刺客实在是太诚信了，他那些诚实的机关令我身上千疮百孔血流如注，但最后他还是没有躲过我的漫天斧影；
战士也很难对付，他召来的鬼魂重重叠叠，杀出重围之后，他依然倒在我的利斧之下；
亚马逊MM是天生战士，但我在她的眼里看到了恐惧，无可否认我当时有一点心软，甚至升起一阵兽欲。后来有传说表明我对她是先奸后杀......
[TOJ]1047自然数序列(2005-08-08 20:02:00)
摘要：自然数序列
Time Limit:1s Memory Limit:32768k
Total Submit:1938 Accepted:1280
下载样例程序(PE)
下载样例程序(ELF)
--------------------------------------------------------------------------------
Problem
题目的描述
有一个由集合{1，2，……，n}（即自然数集的前N项）全体构成的长度为N的无重复项数列，请在每个数字之前加上“+”或“-”构成一个代数式，每个代数式产生一个代数和，输出所有代数和中的最小非负和
In
第1行：一个正整数t，测试数据个数
第2至t+1行：N(N<=1,000,000)
Out
最小非负和，每行一个
Sample Input
2
1
2
Sample Output
1
1
考虑到任意连续的四个自然数可以调整+-号使和为0，这道题就成纸老虎了。
对于任意的n;
1,2,3,...,n
分成这样的一些段
1 ... (n-7,n-6,n-5,n-4),(n-3,n-2,n-1,n)
...
#include<iostream.h>
int main()
{
int w[4]={0,1,1,0};
int n;
long m;
cin>>n;
while(n--)
{
cin>>m;
cout<<w[m%4]<<endl;
}
return 0;
}......
[TOJ]1026整除65的多项式(2005-07-28 18:09:00)
摘要：整除65的多项式
Time Limit:1s Memory Limit:1000k
Total Submit:1749 Accepted:1157
下载样例程序(PE)
--------------------------------------------------------------------------------
Problem
f(x)=5*x^13+13x^5+kax. 输入非负整数k, (k<10000) 找到最小的正整数a,使得对于任意整数x, 65|f(x) 若不存在这样的a,输出 "no" (无引号)
Input
有多组输入，每行一个k.
Output
每行输出一个a
Sample Input
9
Sample Output
63
Source
fairfox
我喜欢这道题，因为它的数学性质重一些，我在纸上算了半天，结果编了一小段程序搞定，虽然很简单我还是把我的推导过程写一下。
用到的数学知识就是初等数论吧，虽然我还没学，就我所了解的（初中的时候数学竞赛有介绍同余理论）做了一些推理得出的。
首先观察出65=5*13，５和13都是素因数，假设f(x)被65整除，那么f(x)一定能被5整除，因为f(x)=5*x^13+13x^5+kax，所以马上得到，一定满足13x^5+kax被5整除，同样的道理可以得到5x^13+kax一定要被13整除。我引这样一种记法，如果一个数n被数m除余r的话，即n%m==r，那么记为n≡r(mod m)。
这样的式子称为同余式，同余式跟等式在运算上非常的相似，有如下一些运算定律：
如果
n1≡r1(mod m)
n2≡r2(mod m)
那么
n1+n2≡r1+r2(mod m)
n1*n2≡r1*r2(mod m)
n1^k≡r1^k(mod m) [k=0,1,2...]
这就是一把刀，下面操刀解题。
继续前面的过程：
现在我们有，如果f(x)能被65整除，那么一定有：
13x^5+kax≡0(mod 5)
5x^13+kax≡0(mod 13)
以13x^5+kax≡0(mod 5)为例，可以写成x(13x^4+ka)≡0(mod 5)，下面按同余的运算定律对x进行分类，x为任意整数，对于模......
[TOJ]1138多项式乘法(2005-07-20 15:42:00)
摘要：多项式乘法
Time Limit:1s Memory Limit:500k
Total Submit:215 Accepted:94
--------------------------------------------------------------------------------
Problem
请编程序把含有乘法运算的代数多项式表达式改写成不含乘法的代数多项式。为简化计算，特做以下约定： (1) 代数多项式表达式中只涉及一个代数符号a； (2) 含有乘法运算的代数多项式表达式都是两个不含乘法运算的代数多项式直接相乘的形式，而且这两个参加乘法的代数多项式都用圆括号括起来了。乘法用符号表示，不得省略。 (3) 常数项以外的各项都是ya^x的形式，其中x为该项的系数，而y是该项的指数。1=x 时，不得简写成ya^，应写成ya^1。而1=y时，不得简写成a^x，应写成1a^x。
Input
输入：每行一个含有乘法的代数多项式表达式。本题有多组数据。
Output
输出：每行输出一个问题的解。要求指数大的项不能出现在指数小的项之后，指数相同的项必须合并同类项。不允许出现不必要的空白字符。
Sample Input
(5a^2+3a^1+2)*(4a^1+1)
(5a^1+1)* (5a^1+1)
Sample Output
20a^3+17a^2+11a^1+2
25a^2+10a^1+1
#include<iostream.h>
struct polynode
{
polynode *next;
int a,e;//ax^e
};
class poly
{
protected:
polynode *head,*tail;
void additem(char*);
void add(int,int);
public:
poly(){head=tail=NULL;};
poly(char*);......