日志分类：算法
#define FALSE 0
#define TRUE 1
#define N 2 /* 进程数 */
int turn; /* 轮到谁了? */
int interested[N]; /* 所有值初始为0（FALSE）*/
void enter_region(int process) /* 进程号为0或1 */
{
int other; /* 另一个进程的进程号 */
other = 1 - process; /* 另一个进程 */
interested[process] = TRUE; /* 标识出希望进入临界区 */
...
发表评论 »
S是初始向量，R是答案向量，A转换矩阵，那么有
R=S*A+S*A^3+S*A^5+...+S*A^(2k+1)
因为矩阵运算满足结合律和分配律
所以有
R=S*A*(I+A^2+A^4+A^6+...+A^(2k))
两边右乘(A^2-I)
得到
R*(A^2-I) = S*A*(I+A^2+A^4+A^6...+A^(2k))*(A^2-I)
根据结合律 和分配律
得到
R*(A^2-I) = S*A*( A^(2k+2) -I)
所以
R= S*A*(A^(2k+2)-I)* (A^2-I)^(-1)
:-)
发表评论 »
2008-10-11，星期六 | 分类：
算法,
转载 | 标签：
算法 | 138 views
我们经常使用的数的进制为“常数进制”，即始终逢p进1。例如，p进制数K可表示为 K = a0*p^0 + a1*p^1 + a2*p^2 + ... + an*p^n （其中0 <= ai <= p-1），它可以表示任何一个自然数。 对于这种常数进制表示法，以及各种进制之间的转换大家应该是很熟悉的了，但大家可能很少听说变进制数。这里我要介绍一种特殊的变进制数，它能够被用来实现全排列的Hash函数，并且该Hash函数能够实现完美的防碰撞和空间利用（不会发生碰撞，且所有空间被完全使用，不多不少）。这种全排列Hash函数也被称为全排列数化技术。下面，我们就来看看这种变进制数。 我们考查这样一种变进制数：第1位逢2进1，第2位逢3进1，……，第n位逢n+1进1。它的表示形式为 K = a1*1! + a2*2! + a3*3! + ... + an*n! （其中0 <= ai <= i），也可以扩展为如下形式（因为按定义a0始终为0），以与p进制表示相对应： K = a0*0! + a1*1! + a2*2! + a3*3! + ... + an*n! （其中0 <= ...
发表评论 »