博文
约瑟夫环问题算法集锦(2008-12-05 12:41:00)
摘要：/*
Name: 约瑟夫环问题算法集锦
Copyright: 始发于goal00001111的专栏；允许自由转载，但必须注明作者和出处
Author: goal00001111搜集整理
Date: 03-12-08 18:14
Description:
有编号从1到N的N个人坐成一圈报数，报到M的人出局，下一位再从1开始， 如此持续，
直止剩下一位为止，报告此人的编号X。
输入N,M，求出X。
共搜集整理了7类10种算法，对于初学者和算法爱好者来说——看了绝对值！
*/
#include<iostream>
#include <time.h>
using namespace std;
int Fun_1(int n, int m);
int Fun_2(int n, int m);
int Fun_3(int n, int m);
int Fun_4(int n, int m);
int Fun_5(int n, int m);
int Fun_6(int n, int m);
int Fun_7(int n, int m);
int Fun_8(int n, int m);
int Fun_9(int n, int m);
int Fun_10(int n, int m);
int main(int argc, char* argv[])
{
int n, m;
//cout << "Input max, step: ";
// cin >> n >> m;
time_t startTime;
time_t endTime;
time(&star......
杨辉三角算法集锦(2008-11-27 19:18:00)
摘要：/*
Name: 杨辉三角算法集锦
Copyright: 始发于goal00001111的专栏；允许自由转载，但必须注明作者和出处
Author: goal00001111
Date: 27-11-08 19:04
Description:
分别使用了二维数组，一维数组，队列，二项式公式，组合公式推论和递归方法等9种算法
算法思路详见代码注释——注释很详细，呵呵
*/
#include<iostream>
#include<iomanip>
using namespace std;
const int MAXROW = 40;
void PrintBlank(int n);
int Com(int n, int m);
int Try(int row, int cel);
void Fun_1(int row);
void Fun_2(int row);
void Fun_3(int row);
void Fun_4(int row);
void Fun_5(int row);
void Fun_6(int row);
void Fun_7(int row);
void Fun_8(int row);
void Fun_9(int row);
int main()
{
int row;
cin >> row;
Fun_1(row);
cout << endl;
Fun_2(row);
cout << endl;
Fun_3(row);
&nb......
有序全排列生成算法(2008-11-21 14:10:00)
摘要：有序全排列生成算法
作者：goal00001111（高粱） 写本文的动力来自一个NOI题目：输出n个数的第m种全排列。
输入两个自然数m,n 1<=n<=20，1<=m<=n!
输出n个数的第m种全排列。
要解决这个问题，必须要生成有序的全排列。
生成n个
数字的全排列是算法学习中的一个经典案例，也是信息学奥赛中的一个常考内容，值得我们去深入研究。生成全排列的算法很多，大概分类有直接模拟法，设置中介
数法和数学分析法（这是我杜撰的一个名称），其中直接模拟法又可以分为递归和非递归模拟。设置中介数后，更是可以分为字典序全排列生成法，递增进位排列生
成算法，递减进位排列生成算法和循环左移排列生成算法等类别。此外还有邻位对换法和邻元素增值法等另类生成方法。利用这些算法生成的全排列，有些是有序全
排列，有些却是无序的，本文主要探讨有序全排列。
在上面列举的算法中，字典序全排列生成法和邻元素增值法，以及我杜撰的数学分析法可以生成有序全排列，即可以输出n个数的第m种全排列。其中字典序全排列
生成法根据是否设置中介数又可以分为两类，不用设置中介数的方法即直接模拟法。
我
们首先来看最简单的递归直接模拟法。这是普通递归方法的一个改进。普通的递归方法是利用将当前数组左界元素与其右侧的元素交换位置来实现排列，这样得到的
全排列是无序的。所以我们不能直接调换位置，而是将左界右侧的元素顺序右移，不破坏原排列的顺序，保证右侧元素的递增性。
为了回答本文开头提出的问题，我们统一设置一个接口void Permutation(long long n, long long
m);其中n表示共n个自然数，m表示第m种全排列。
在子程序中我们先创建一个数组a[n]来存储n个自然数，然后递归查找并输出n个数的第m种全排列。下面是主要的代码：（完整的代码附在文章后面，下同）
/*
函数名称：Permutation
函数功能：输出n个数的第m种全排列
输入变量：long long n：1，2，3，...，n共n个自然数（1<=n<=20） long long
m：第m种全排列（1<=m<=n!） 输出变量：无 */
void Permutation(long long n, long long m)// 递归直接模拟法......
凯撒密码(2008-10-25 20:37:00)
摘要：/*
Name:
Copyright:
Author:
Date: 25-10-08 20:34
Description:
凯撒密码（caeser）是罗马扩张时期朱利斯o凯撒（Julius Caesar）创造的，用于加密通过信使传递的作战命令。
它将字母表中的字母移动一定位置而实现加密。注意26个字母循环使用，z的后面可以堪称是a。
凯撒密码的加密算法极其简单。其加密过程如下：
在这里，我们做此约定：明文记为m，密文记为c，加密变换记为E(key1,m)（其中key1为密钥），
解密变换记为D(key2,m)（key2为解密密钥）（在这里key1=key2,不妨记为key）。
凯撒密码的加密过程可记为如下一个变换：c≡m+key (mod n） （其中n为基本字符个数）
同样，解密过程可表示为：m≡c+key (mod n） （其中n为基本字符个数）
*/
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
using namespace std;
bool ReadFile(vector<string> & article, char * fileName);
bool WriteFile(const vector<string> & article, char * fileName);
void Encrypt(const vector<string> & proclaimedInWriting, vector<string> & cryptograph, int key);
void Decode(const vector<string> & cryptograph, vector<string> & proclaimedInWritin......
模运算及其应用(2008-10-25 11:59:00)
摘要：
模运算及其应用
goal00001111搜集整理
摘要：模运算在数论和程序设计中应用很广泛，从奇偶数的判别到素数的判别，从模幂运算到最大公约数的求法，从孙子问题到凯撒密码问题，无不充斥着模运算的身影。本文从模运算的概念，性质，到模运算的基本应用，较为全面的介绍了模运算及其编程方法。
关键词：模运算 程序设计
应用
模运算在数论和程序设计中都有着广泛的应用，从奇偶数的判别到素数的判别，从模幂运算到最大公约数的求法，从孙子问题到凯撒密码问题，无不充斥着模运算的身影。虽然很多数论教材上对模运算都有一定的介绍，但多数都是以纯理论为主，对于模运算在程序设计中的应用涉及不多。本文以c++语言为载体，对基本的模运算应用进行了分析和程序设计，以理论和实际相结合的方法向大家介绍模运算的基本应用。。
一 基本理论：
基本概念：
给定一个正整数p，任意一个整数n，一定存在等式 n = kp + r
；
其中k、r是整数，且 0 ≤ r < p，称呼k为n除以p的商，r为n除以p的余数。
对于正整数p和整数a,b，定义如下运算：
取模运算：a % p（或a mod p），表示a除以p的余数。
模p加法：(a + b) % p ，其结果是a+b算术和除以p的余数，也就是说，(a+b) = kp +r，则(a + b) % p = r。
模p减法：(a-b) % p ，其结果是a-b算术差除以p的余数。
模p乘法：(a * b) % p，其结果是 a * b算术乘法除以p的余数。
说明：
1. 同余式：正整数a，b对p取模，它们的余数相同，记做 a ≡ b % p或者a ≡ b (mod p)。
2. n % p得到结果的正负由被除数n决定,与p无关。例如：7%4 = 3， -7%4 = -3， 7%-4 = 3， -7%-4 = -3。
二进制在数学中的妙用(2008-06-15 16:39:00)
摘要：
二进制在数学中的妙用
goal00001111搜集整理
十八世纪初，莱布尼茨发明了二进制数，当时的他肯定没有预料到二进制在信息时代会有着如此广泛的应用。二进制数以其工作可靠，运算简单，逻辑严密，容易实现等特点，成为了计算机的专用语言。在计算机科学和大量应用数学领域中，二进制记数法是必不可少的。在趣味数学方面，同样也有广泛的应用。
让我们先来看一个经典的数学趣题：
一工人工作7天，老板有一段黄金，每天要给工人1/7的黄金作为工资，老板只能切这段黄金2刀，请问怎样切才能每天都给工人1/7的黄金？
这题不简单吧？小心别把脑子都想破了。
在给出答案之前，先让我们看另一个简单的例子：
用天平称1~63克整数克重的物品，至少要配备几只多重的砝码（砝码只能放在天平的一端）？
没有学过二进制的人是很难想到答案的，可是如果你知道二进制数，那就不难了。我们知道二进制中只有0和1两个数字，它的各位数字的权值从小到大依次为2^0，2^1，2^2，2^3，。。。。我们用一个数的每位数字乘以其权值所得到的乘积之和来表示这个数。对于一个具有8位的二进制数来说，它可以表示的数据范围是0~2^8。
63 = 2^6 – 1 =
2^0 + 2^1 + 2^2 + 2^3 + 2^4 + 2^5
所以，我们只需配备2^0 =1，2^1 = 2，2^2 = 4，2^3 = 8，2^4 = 16，2^5 = 32五种不同克数的砝码各一个。
类似的题目还有如何装苹果：
现有一笔出售苹果的生意，已知客人可能需要的苹果数量肯定是1个到1000个之间，但不知道具体数字。客人要求必须全部用他提供的箱子装整箱（每个箱子都最多可以装1000个苹果），箱子一旦装成就无法再拆开重装。
你手中有1000个苹果，10个箱子，客人需要的苹果数量未知，问怎么装才能满足客人的需要？
解题的原理和上题是一样的，都是利用二进制数的记数原理。因为1000 < 2^10 = 1024，所以只要使用2^0，2^1，2^2，2^3，2^4，2^5，2^6，2^7，2^8，2^9十个数，就可以表示1到1023之间的所有数。
例如：30 = 2^1 +......
第53次编程比赛题目研究 (2007-05-25 17:39:00)
摘要：题目:
产生指定长度的无连续重复部分的字符串(所有元素都由'1','2','3'这三个字母构成)
输入: 指定的长度n
输出: 无
函数接口:
void unoverlap(int n, char *p)//p是已经分配好了的,不用担心溢出.
例如:
输入5
输出 p中的内容应为12312(或满足条件的其它串)
(不能输出12323,因为23和23是连在一起的并且相同)
当然只要输出一个满足条件字符串的就可以了。
最容易想到的是回溯法，每放一个数字判断是否会产生重复，按'1','2','3'的顺序放置，
如果都不满足，则回退一个。
代码1如下：（取材于poorb的代码）
bool Cover(char *base, int top)//判断是否有连续重复序列
{
int p;
int k = (top + 1) / 2;
for (int step=1; step<=top; step++)
{
for (p=0; p<step; ++p)
{
if (base[top-p] != base[top-step-p])
break;
}
if (p == step)//产生重复
&nbs......
以空间换时间算法集锦(4)(2007-04-20 14:42:00)
摘要：5．士兵站队
题目：训练场上n(1≤n≤50000)个高矮都不相同的士兵从左到右排成一行，依次编号为1，2，…，n。
第i个士兵的身高H(i)，由于采用特殊单位，H(i)满足1≤H(i)≤2000000000。
设第i个士兵右侧最近的比他个高的士兵编号为j，则第i个士兵可看到在他的右侧比他矮的士兵的个数S(i)=j-i-1。（不考虑客观因素，比如视力范围等-,-）
求S(1)+S(2)+…+S(n)。
输入：
标准输入。
第一行为整数n，表示士兵的个数。
第二行n个整数，用一个空格隔开。分别表示编号为1,2。。。n的士兵的身高
输出：
S(1)+S(2)+…+S(n)的结果
例：
输入
6
10 3 7 4 12 2
输出
5
主函数：
#include <iostream>
#include <time.h>
using namespace std;
int Sum(int h[], int n);
int main(void)
{
time_t startTime;
time_t endTime;
const int n = 50000;
int h[n] = {0};
int temp, p;
//获取互不相同的一组数列
for (int i=0; i<n; i++)
h[i] = i + 1;
for (int i=n-1; i>0; i--)//洗牌，使得数的大小随机排列
{
p = rand()%i;
&......
以空间换时间算法集锦(3)(2007-04-20 14:41:00)
摘要：4．满足条件的m的个数
给出一个数字n和k，请找出有多少个不同的整数m满足：
1） m<2^n
2） m>=0
3） |f(m,n)|<=k
其中f(x,n)的定义如下：
f(0,n)=n;
f(x,n)=f([x/2],n),x为偶数
f(x,n)=f([x/2],n)-2,x为奇数
Input
每组一行，分别给定n,k(1<=n<=62,2<=k<=5)
Output
每组一行，给出满足条件的m的个数
Sample Input
1 2
4 3
Sample Output
2
14
主函数：
#include <iostream>
#include <time.h>
using namespace std;
int Fun(int n, int k);
int main()
{
time_t startTime;
time_t endTime;
time(&startTime);
for (int i=1; i<=20; i++)
for (int j=2; j<=5; j++)
cout << i << "," << j << ": " << Fun(i, j) << "\t";
cout << endl;
time(&endTime);
c......
以空间换时间算法集锦(2)(2007-04-20 14:39:00)
摘要：3．丑陋数
题目来自http://acm.pku.edu.cn/JudgeOnline/problem?id=1338，我做了一点小改动。
丑陋数是指质因数只包含2，3，5的自然数，例如前十个丑陋数依次为：1, 2, 3, 4, 5, 6, 8, 9, 10, 12。
给定一个自然数n (n <= 1500)，请你求出对应的第n个丑陋数。
函数接口：unsigned long UglyNumber(int n);
输入输出示例：
n = 2， 返回 2； n = 5， 返回 5；n = 7， 返回 8； n = 11， 返回 15；
解决此问题的一种思路就是先建立一个丑陋数表，把前1500个丑陋数全部求出来存储到数组lib[]中，这样只要返回lib[n-1]就好了。
本文分析一些建立丑陋数表的方法。
方法一：很容易想到判断一个数是否为丑陋数的方法，那就是判断它的因子是否只包含2，3，5。最简单的方法就是依次判断各个自然数，直到找齐1500个丑陋数为止。
代码如下：
#define MAX 500
unsigned long UglyNumber(int n)
{
unsigned long lib[MAX] = {1,};//用来存储丑陋数表
unsigned long i, num;
int k = 1;
for (i=2; ......