Algorithm - 太阳神上的博客

　　这是另一种矩阵求逆的方法，其基本思想是若对A矩阵求逆，则在其右边附加一个同型的单位矩阵，然后对这个合并了的矩阵进行初等行变换至行最简形，此时再分割这个矩阵，矩阵左边的应该是一个单位矩阵，而右边的则是一就是原来A矩阵的逆。下面是相关的Lua代码，与以前代码相同的部分省略。

-- Merge matrices horizontally
MatrixMeta.merge=function(this,other)
if this.row~=other.row or this.column ~= other.column then
return nil
end
local data={}
for i=1,this.row do
for j=1,this.column do
table.insert(data,this:at(i,j))
end
for j=1,this.column do
table.insert(data,other:at(i,j))
end
end
return Matrix(data,this.row,this.row*2)
end
-- Divide the matrix into two parts
MatrixMeta.divide=function(this)
if this.column~=2*this.row then
return nil
end
local a={}
local b={}
local remainder
for i,v in ipairs(this.data) do
remainder=i%this.column
if remainder~=0 and remainder <= this.column/2 then
table.insert(a,v)
else
table.insert(b,v)
end
end
a=Matrix(a,this.row,this.row)
b=Matrix(b,this.row,this.row)
return a,b
end
-- Another way to get inversed matrix
MatrixMeta.inverse2=function(this)
if this.row ~= this.column or Determinant(this.data):eval()==0 then
return nil
end
local e={}
for i=1,this.row-1 do
table.insert(e,1)
for j=1,this.row do
table.insert(e,0)
end
end
table.insert(e,1)
e=Matrix(e,this.row,this.column)
local merged=this:merge(e)
merged:reduce()
local a,b=merged:divide()
return b
end

这里充分使用了Lua的元表来实现Lua风格的面向对象程序设计，用Lua编程的感觉还是不错的。

#!/usr/bin/env lua
VectorMeta={}
VectorMeta.__add=function(a,b)
local size=table.maxn(a)
assert(size==table.maxn(b))
local data={}
for i=1,size do
table.insert(data,a[i]+b[i])
end
return Vector(data)
end
VectorMeta.__sub=function(a,b)
local size=table.maxn(a)
assert(size==table.maxn(b))
local data={}
for i=1,size do
table.insert(data,a[i]-b[i])
end
return Vector(data)
end
VectorMeta.__mul=function(a,b)
if type(a)=="number" then
local data={}
for _,v in ipairs(b) do
table.insert(data,a*v)
end
return Vector(data)
else
local size=table.maxn(a)
assert(size==table.maxn(b))
local sum=0
for i=1,size do
sum=sum+a[i]*b[i]
end
return sum
end
end
VectorMeta.__index=function(data,index)
if type(index)=="number" then
return data[index]
else
return VectorMeta[index]
end
end
VectorMeta.length=function(data)
local sum=0
for _,v in ipairs(data) do
sum=sum+v*v
end
return math.sqrt(sum)
end
VectorMeta.print=function(this)
io.write('[')
for i=1,table.maxn(this)-1 do
io.write(this[i],',')
end
io.write(this[table.maxn(this)],"]\n")
end
-- Use Schmitt method to orthogonalize vectors
VectorMeta.orthogonalize=function(...)
local alphas=arg
local betas={arg[1]}
for i=2,table.maxn(alphas) do
local beta=alphas[i]
for j=1,i-1 do
beta=beta-((alphas[i]*betas[j])/(betas[j]*betas[j]))*betas[j]
end
assert(type(beta)=="table")
table.insert(betas,beta)
end
return betas
end
Vector=function(data)
setmetatable(data,VectorMeta)
return data
end

矩阵的运算是通过Lua的metatable来完成的，用起来和C++的操作符重载一样方便，而矩阵的求逆就是通过求伴随矩阵再除以其行列式的值而得。即

$A^{-1}=\frac{1}{|A|}A^{*}$

在实现过程中遇到了一些麻烦，有一个是我的对于伴随矩阵的理解有问题，原来伴随矩阵不仅仅要每个元素由其代数余子式代替，还得转置一下。

#!/usr/bin/env lua
require 'determinant'
function Matrix(data,row,column)
local size=table.maxn(data)
assert(size==row*column)
local matrix={}
matrix.data=data
matrix.row=row
matrix.column=column
matrix.at=function(this,row,column)
return this.data[(row-1)*this.column+column]
end
matrix.set=function(this,row,column,num)
this.data[(row-1)*this.column+column]=num
end
matrix.swaprow=function(this,r1,r2)
local temp
for i=1,this.column do
temp=this:at(r1,i)
this:set(r1,i,this:at(r2,i))
this:set(r2,i,temp)
end
end
matrix.simplifycolumn=function(this,column,layer)
if this:at(layer,column) == 0 then
for i=layer+1,this.row do
if this:at(i,column) ~= 0 then
this:swaprow(i,layer)
break
end
end
end
if this:at(layer,column) == 0 then
return layer
end
for i=1,this.row do
if i~= layer then
local tomultiply=-this:at(i,column)/this:at(layer,column)
for j=1,this.column do
this:set(i,j,this:at(layer,j)*tomultiply+this:at(i,j))
end
end
end
return layer+1
end
matrix.swapcolumn=function(this,c1,c2)
local temp
for i=1,this.row do
temp=this:at(i,c1)
this:set(i,c1,this:at(i,c2))
this:set(i,c2,temp)
end
end
matrix.simplifyrow=function(this,row,layer)
if this:at(row,layer) == 0 then
for i=layer+1,this.column do
if this:at(row,i) ~= 0 then
this:swapcolumn(i,layer)
break
end
end
end
if this:at(row,layer) == 0 then
return layer
end
for i=1,this.column do
if i ~= layer then
local tomultiply=-this:at(row,i)/this:at(row,layer)
for j=1,this.row do
this:set(j,i,this:at(j,layer)*tomultiply+this:at(j,i))
end
end
end
return layer+1
end
-- Make the matrix to reduced form
matrix.reduce=function(this)
local layer=1
for i=1,this.column do
layer=this:simplifycolumn(i,layer)
if layer>this.row then
break
end
end
for i=1,this.row do
local tomultiply=nil
for j=1,this.column do
if tomultiply then
this:set(i,j,this:at(i,j)*tomultiply)
elseif this:at(i,j)~= 0 then
tomultiply=1/this:at(i,j)
this:set(i,j,1)
end
end
end
end
-- Make the matrix to canonical form
matrix.canonicalize=function(this)
this:reduce()
local layer=1
for i=1,this.row do
layer=this:simplifyrow(i,layer)
if layer>this.column then
break
end
end
end
-- Get the rank of the matrix
-- Matrix should be reduced before.
matrix.rank=function(this)
local rank=0
for i=1,this.row do
for j=1,this.column do
if this:at(i,j) ~= 0 then
rank=rank+1
break
end
end
end
return rank
end
matrix.print=function(this)
for i=1,this.row do
for j=1,this.column do
io.write(this:at(i,j),'\t')
end
io.write('\n')
end
end
-- Get the transposed matrix
matrix.transpose=function(this)
local data={}
for i=1,this.column do
for j=1,this.row do
table.insert(data,this:at(j,i))
end
end
return Matrix(data,this.column,this.row)
end
matrix.cofactor=function(this,row,column)
local data={}
for i=1,this.row do
for j=1,this.column do
if i~=row and j~=column then
table.insert(data,this:at(i,j))
end
end
end
if (row+column)%2==0 then
return Determinant(data):eval()
else
return -Determinant(data):eval()
end
end
-- Get the adjoint matrix of this matrix
matrix.adjoint=function(this)
local data={}
for i=1,this.row do
for j=1,this.column do
table.insert(data,this:cofactor(i,j))
end
end
return Matrix(data,this.row,this.column):transpose()
end
-- Get the inverse matrix of this matrix
-- If this matrix is not invertible, nil is returned
matrix.inverse=function(this)
-- Only array can be invertible
if this.row ~= this.column then
return nil
end
local det=Determinant(this.data):eval();
if det==0 then
return nil
end
return (1/det)*this:adjoint()
end
if MatrixCalc then
setmetatable(matrix,MatrixCalc)
end
return matrix
end
-- The matrix calculation metatable
MatrixCalc={}
MatrixCalc.__add=function(a,b)
assert(a.row==b.row and a.column==b.column)
local data={}
for i=1,a.row*a.column do
table.insert(data,a.data[i]+b.data[i])
end
return Matrix(data,a.row,a.column)
end
MatrixCalc.__sub=function(a,b)
assert(a.row==b.row and a.column==b.column)
local data={}
for i=1,a.row*a.column do
table.insert(data,a.data[i]-b.data[i])
end
return Matrix(data,a.row,a.column)
end
MatrixCalc.__unm=function(a)
local data={}
for i=1,a.row*a.column do
table.insert(data,-a.data[i])
end
return Matrix(data,a.row,a.column)
end
MatrixCalc.__mul=function(a,b)
if tonumber(a) then
-- a is a number
local data={}
for i=1,b.row*b.column do
table.insert(data,a*b.data[i])
end
return Matrix(data,b.row,b.column)
else
-- a is a matrix
assert(a.column==b.row)
local data={}
for i=1,a.row do
for j=1,b.column do
local value=0
for m=1,a.column do
value=value+a:at(i,m)*b:at(m,j)
end
table.insert(data,value)
end
end
return Matrix(data,a.row,b.column)
end
end
MatrixCalc.__eq=function(a,b)
if a.row~=b.row or a.row~=b.column then
return false
end
for i=1,a.row*a.column do
if a.data[i]~=b.data[i] then
return false
end
end
return true
end

#!/usr/bin/env lua
function Matrix(data,row,column)
local size=table.maxn(data)
assert(size==row*column)
local matrix={}
matrix.data=data
matrix.row=row
matrix.column=column
matrix.at=function(this,row,column)
return this.data[(row-1)*this.column+column]
end
matrix.set=function(this,row,column,num)
this.data[(row-1)*this.column+column]=num
end
matrix.swaprow=function(this,r1,r2)
local temp
for i=1,this.column do
temp=this:at(r1,i)
this:set(r1,i,this:at(r2,i))
this:set(r2,i,temp)
end
end
matrix.simplifycolumn=function(this,column,layer)
if this:at(layer,column) == 0 then
for i=layer+1,this.row do
if this:at(i,column) ~= 0 then
this:swaprow(i,layer)
break
end
end
end
if this:at(layer,column) == 0 then
return layer
end
for i=1,this.row do
if i~= layer then
local tomultiply=-this:at(i,column)/this:at(layer,column)
for j=1,this.column do
this:set(i,j,this:at(layer,j)*tomultiply+this:at(i,j))
end
end
end
return layer+1
end
matrix.swapcolumn=function(this,c1,c2)
local temp
for i=1,this.row do
temp=this:at(i,c1)
this:set(i,c1,this:at(i,c2))
this:set(i,c2,temp)
end
end
matrix.simplifyrow=function(this,row,layer)
if this:at(row,layer) == 0 then
for i=layer+1,this.column do
if this:at(row,i) ~= 0 then
this:swapcolumn(i,layer)
break
end
end
end
if this:at(row,layer) == 0 then
return layer
end
for i=1,this.column do
if i ~= layer then
local tomultiply=-this:at(row,i)/this:at(row,layer)
for j=1,this.row do
this:set(j,i,this:at(j,layer)*tomultiply+this:at(j,i))
end
end
end
return layer+1
end
-- Make the matrix to reduced form
matrix.reduce=function(this)
local layer=1
for i=1,this.column do
layer=this:simplifycolumn(i,layer)
if layer>this.row then
break
end
end
for i=1,this.row do
local tomultiply=nil
for j=1,this.column do
if tomultiply then
this:set(i,j,this:at(i,j)*tomultiply)
elseif this:at(i,j)~= 0 then
tomultiply=1/this:at(i,j)
this:set(i,j,1)
end
end
end
end
-- Make the matrix to canonical form
matrix.canonicalize=function(this)
this:reduce()
local layer=1
for i=1,this.row do
layer=this:simplifyrow(i,layer)
if layer>this.column then
break
end
end
end
-- Get the rank of the matrix
-- Matrix should be reduced before.
matrix.rank=function(this)
local rank=0
for i=1,this.row do
for j=1,this.column do
if this:at(i,j) ~= 0 then
rank=rank+1
break
end
end
end
return rank
end
matrix.print=function(this)
for i=1,this.row do
for j=1,this.column do
io.write(this:at(i,j),'\t')
end
io.write('\n')
end
end
return matrix
end

　　这是书上１.４的内容，进度得加快

#!/usr/bin/env lua
require 'determinant'
function Cramer(n)
assert(n>0)
local cramer={}
-- the coefficient determinant
cramer.D={}
-- this D1,D2,D3...
cramer.Ds={}
for i=1,n do
table.insert(cramer.Ds,{})
end
-- this number of unknown numbers
cramer.n=n
-- add an equation
-- for example:
-- x1+2x2-x3+3x4=2
-- use cramer:add(1,2,-1,3,2)
cramer.add=function(this,...)
local toadd={...}
assert(table.maxn(toadd)==this.n+1)
for i=1,this.n do
table.insert(this.D,toadd[i])
for j=1,this.n do
table.insert(this.Ds[j],toadd[i])
end
end
local last=toadd[this.n+1];
local times=table.maxn(this.D)/this.n
for i=1,this.n do
this.Ds[i][(times-1)*this.n+i]=last
end
end
-- Use Cramer Rules to solve linear equations
-- When solution does not exist, nil is returned,
-- and solution table returned otherwise.
cramer.solve=function(this)
assert(table.maxn(this.D)==this.n*this.n)
local D=Determinant(this.D):eval();
if D==0 then
return nil
end
local solutions={}
local Dn;
for i=1,this.n do
Dn=Determinant(this.Ds[i]):eval();
table.insert(solutions,Dn/D)
end
return solutions;
end
return cramer
end

下面是一个例子：

cramer=Cramer(4)
cramer:add(1,2,-1,3,2)
cramer:add(2,-1,3,-2,7)
cramer:add(0,3,-1,1,6)
cramer:add(1,-1,1,4,-4)
solutions=cramer:solve()
for _,v in ipairs(solutions) do
print(v)
end

输出是１，３，２，-１，符合书上答案

复习线性代数，写了一个计算行列式的Lua脚本：

#!/usr/bin/env lua
-- This is the constructor of a determinant
-- It get an array of numbers as argument
-- And add methods for it
function Determinant(data)
local det={}
det.row=math.sqrt(table.maxn(data))
-- If the number is not proper, raise error
if math.floor (det.row) ~= det.row then
error("Determinant's data number must be n^2!")
end
det.data=data
-- index function
det.at=function(this,row,column)
return this.data[(row-1)*this.row+column];
end
det.cofactor=function(this,row,column)
local cofactor={}
local r=1
local c=0
for _,v in ipairs(this.data) do
c=c+1;
if c==this.row+1 then
r=r+1
c=1
end
if not (r==row or c==column) then
table.insert(cofactor,v)
end
end
return cofactor
end
-- evaluation function
det.eval=function(this)
local a=this.data
-- this is the simplest case
if this.row==2 then
return a[1]*a[4]-a[2]*a[3]
-- for accerleration
elseif this.row==3 then
return a[1]*a[5]*a[9]+a[3]*a[4]*a[8]+a[2]*a[6]*a[7]-a[3]*a[5]*a[7]-a[1]*a[6]*a[8]-a[2]*a[4]*a[9]
else
local value=0
local cofactor=0
local add=true
for i=1,this.row do
cofactor=Determinant(this:cofactor(1,i))
cofactor=this.data[i]*cofactor:eval()
if add then
value=value+cofactor
else
value=value-cofactor
end
add = not add
end
return value
end
end
return det
end

　　最近，我用Lua写了一个算24点的算法，这个算法的思想很简单，就是不断穷举表达式，然后计算每个表达式的值是否为24。如果为24，则输出。问题的难点在于如何穷举表达式，我的做法是将要处理的数和另外穷举出的运算符组成一个含有七个元素的数组（四个操作数，三个操作符），然后遍历这个数据的全排列，将每个排列看成一个逆波兰式，如果计算成功，则将逆波兰式再转成中辍表达式输出。这个算法有一个明显的缺点，它会产生很多冗余的式子（即形式不同，但运算实质相同）。

#!/usr/bin/env lua
 
-- used for store four points
array={}
 
-- reverse the whole array from first to last
function array.reverse(this,first,last)
        first = first or 1
        last = last or table.maxn(this)
        while first < last do
                this[first],this[last]=this[last],this[first]
                first=first+1
                last=last-1
        end
end
 
-- this algorithm is modified from the C++ STL
-- change array to next permutation and returns true
-- return false if the current is the last permutation 
function array.next_permutation(this,first,last)
        local len=table.maxn(this)
        if len==0 or len==1  then
                return false
        end
 
        first = first or 1
        last = last or len
       
        local i=last
        while true do
                local ii=i
                i=i-1
                if this[i] < this[ii] then
                        local j=last
                        while this[i] >= this[j] do
                                j=j-1
                        end
                        this[i],this[j]=this[j],this[i]
                        this:reverse(ii,last)
                        return true
                end
 
                if i==first then
                        return false
                end
        end
end
 
-- show the array with space seperated
function array.show(this)
        for _,i in ipairs(this) do
                io.write(i,' ')
        end
        io.write('\n')
end
 
optable={"+","-","*","/"}
opfuncs={}
opfuncs["+"]=function(a,b)
        return a+b
end
 
opfuncs["-"]=function(a,b)
        return a-b
end
 
opfuncs["*"]=function(a,b)
        return a*b
end
 
opfuncs["/"]=function(a,b)
        if b==0 then
                return nil
        else
                return a/b
        end
end
 
 
-- stack class for calculation
function Stack()
        local stack={}
        stack.push=table.insert
        stack.pop=table.remove
        stack.size=table.maxn
        stack.bottom=function(this)
                return this[1]
        end
        return stack
end
 
-- calculate from polish notation
function array.eval(toeval)
        local stack=Stack()
        for _,v in ipairs(toeval) do
                local op=opfuncs[v]
                if op then
                        if stack:size() <2 then
                                return nil
                        end
                        local b=stack:pop()
                        local a=stack:pop()
                        local result=op(a,b)
                        if result then
                                stack:push(result)
                        else
                                return nil
                        end
                else
                        stack:push(tonumber(v))
                end
        end
 
        return stack:bottom()
end
 
-- precedence table, "n" is number
precedence={
        ["+"] = 1;
        ["-"] = 1;
        ["*"] = 2;
        ["/"] = 2;
        ["n"] = 3;
}
 
-- convert from polish expression to normal expression
function array.show_expr(this)
        local strStack=Stack()
        local typeStack=Stack()
       
        for _,v in ipairs(this) do
                if opfuncs[v] then
                        local b=strStack:pop()
                        local a=strStack:pop()
 
                        local bp=precedence[typeStack:pop()]
                        local ap=precedence[typeStack:pop()]
                        local vp=precedence[v]
                       
                        if ap<=vp then
                                a="("..a..")"
                        end
 
                        if bp<=vp then
                                b="("..b..")"
                        end
 
                        strStack:push(a..v..b)
                        typeStack:push(v)
                else
                        strStack:push(v)
                        typeStack:push("n")
                end
        end
        print(strStack:bottom())
end
 
 
-- get table copy(contains its methods)
function array.copy(this)
        local copy={}
        for index,value in pairs(this) do
                copy[index]=value
        end
        return copy
end
 
-- the main method to calculate 24 points 
function array.calc(this)
        local order=1
        for i=1,4 do
                for j=i,4 do
                        for k=j,4 do
                                local toeval=this:copy()
                                table.insert(toeval,optable[i])
                                table.insert(toeval,optable[j])
                                table.insert(toeval,optable[k])
                                table.sort(toeval)                       
                                while true do
                                        if tostring(toeval:eval())=="24" then
                                                io.write(order,": ")
                                                toeval:show_expr()
                                                order=order+1
                                        end
 
                                        if not toeval:next_permutation() then
                                                break
                                        end
                                end
                        end
                end
        end
end
 
for i=1,4 do
        if not arg[i] then
                io.stderr:write("Please input at least four arguments!\n")
                return 1
        end
 
        local num=tonumber(arg[i])
        if not num then
                io.stderr:write("Arguments must be numbers\n")
                return 2
        end
       
        if num<1 or num > 13 then
                io.stderr:write("Number must in [1,13]\n")
                return 3
        end
 
        if math.floor(num)~=num then
                io.stderr:write("Number must be an integer!\n")
                return 4
        end
 
        table.insert(array,arg[i])
end
 
array:calc()

　　上次我把程序发给了另外一个高中同学，他似乎并没有花多少时间就找出来了。但是看他给我的描述，似乎找到不是真正的存放关键数据的内存。还是给廖传政同学修改的差不多，由于要通过画矩形来显示结果，所以必定要提供一个变量来表示真实的数据。如果放在一个函数的局部变量里，由于局部变量是存放在栈中的，只要调用堆栈相同就可以找到。所以放在堆空间更好，但是我却忽略了一点。如下：

void *p=malloc(100);
free(p);
p=malloc(100)

　　这个式子中，p在free前后的值很多情况下是相同的，这样，即使在堆空间，也可能完全相同。为了防止这种情况，我又使用了随机得到一个堆内存的方法，为了防止栈空间也相同，我同样使用了随机层次的递归，这样一来，我觉得应该会提高破解的难度。更新的代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
 
#include <SDL/SDL.h>
 
SDL_Surface *screen = NULL;
int blood;
 
int *encode;
int *decode;
SDL_Rect *rects;
 
int index_of(int array[],size_t size,int value){
    int index;
    for(index=0;index<size;index++){
        if(array[index]==value)
            return index;
    }
    return -1;
}
 
 
void begin_game(){
    srand(time(NULL));
    encode=(int *)malloc(1024*sizeof(int));
    decode=(int *)malloc(1024*sizeof(int));
    rects=(SDL_Rect *)malloc(1024*sizeof(SDL_Rect));
   
    int i,r;
    for(i=0;i<101;i++){
        r=rand()%101;
        if(index_of(encode,i,r)==-1)
            encode[i]=r;
        else{
            i--;
            continue;
        }           
    }
   
    for(i=0;i<101;i++){
        decode[i]=index_of(encode,101,i);
    }   
   
    blood=encode[100];
}
 
void end_game(){
    free(encode);
    free(decode);
    free(rects);
}
 
void draw (int layer){
    if(layer>0)
        return draw(--layer);
   
    Uint32 color;   
    color=SDL_MapRGB(screen->format,0,0,0);
    SDL_FillRect (screen, NULL, color);   
    color = SDL_MapRGB (screen->format, 0xFF, 0, 0);
   
    SDL_Rect *rect=&rects[rand()%1024];
    rect->w = decode[blood]*5;
    rect->h = 20;
    rect->x = 100;
    rect->y = 100;
    SDL_FillRect (screen, rect, color);
 
    SDL_Flip (screen);
    SDL_Delay (10);
}
 
 
 
 
int main (int argc, char *argv[]){
    char *msg;
    int done;
   
    SDL_Init (SDL_INIT_VIDEO);
    atexit (SDL_Quit);
 
    screen = SDL_SetVideoMode (640, 480, 16, SDL_SWSURFACE | SDL_DOUBLEBUF);
    SDL_WM_SetCaption ("SDL MultiMedia Application", NULL);
    begin_game();
   
 
    done = 0;
    SDL_Event event;
   
    while (!done){
        SDL_WaitEvent (&event);
        switch (event.type){
            case SDL_KEYDOWN:{
                switch(event.key.keysym.sym){
                    case SDLK_UP:blood = decode[blood]+10>100 ? blood : encode[decode[blood]+10];break;
                    case SDLK_DOWN:blood = decode[blood]-10<0 ? blood : encode[decode[blood]-10];break;
                }
            }
                break;
            case SDL_QUIT:
                done = 1;
                break;
            default:
                break;
        }
        draw (rand()%10);
    }
   
    end_game();
 
    return 0;
}
 

　　前几天我看到廖传政又在修改游戏，于是就给他较劲，故意编个游戏来让他修改不了。据他说，假如要让血槽不动，一般是找到内存变化的地方，然后锁定就是了。从这一点出发，我想到如果表示内存变化的那个地方完全没的规律，那么就比较难以查找了。
　　我的想法是，真实的数据不能直接放在内存中，而是代之以一个神秘的数值，这个神秘的数值也完全零乱，也就是说血条上升或下降时，这个值会变化，但不一定也是上升或是下降，也是就他们之间不存在简单的线性关系，更进一步说，如果把这个神秘数与真实数的对应关系是一个函数的话，那这个函数是非线性的，其实光线性还不够，而且要是找不出单调的区间。但是它们之间又要可逆，就是要找出一个可逆的非单调函数。
　　我的基本思想是，假如要加密的是0到100之间的整数，那么就先生成把0到100随机存放到一个encode数组，作为加密的数组，例如一个真实数56，它所对应的加密数就是encode[56]，然后产生一个解密数组，分别存放0到100在encode数组中的索引，也就是for any i in 0..100,encode[decode[i]]=i。如果把encode看成是一个函数，那它的逆函数就是decode。
　　真正在内存里保存的数都是那个“神秘数”，而真实数都得通过decode数组才能读出，通过encode来写，由于加密和解密的部分都只是几次寻址操作，所以效率并不低，而且我们只对关键的数值进行加密。其它不管。
　　这个算法我给他做了以后，他算是半个成功了，因为找到了那个显示血槽对象的相关内存，但是真正存放数据的地方却没有找到。本来游戏是用Irrlicht写的3D，很占内存和CPU，下面是我用SDL改写的，完全只保留了最基本的演示：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
 
#include <SDL/SDL.h>
 
SDL_Surface *screen = NULL;
int blood;
 
int *encode;
int *decode;
 
int index_of(int array[],size_t size,int value){
    int index;
    for(index=0;index<size;index++){
        if(array[index]==value)
            return index;
    }
    return -1;
}
 
 
void begin_game(){
    srand(time(NULL));
    encode=(int *)malloc(1024*sizeof(int));
    decode=(int *)malloc(1024*sizeof(int));
   
    int i,r;
    for(i=0;i<101;i++){
        r=rand()%101;
        if(index_of(encode,i,r)==-1)
            encode[i]=r;
        else{
            i--;
            continue;
        }           
    }
   
    for(i=0;i<101;i++){
        decode[i]=index_of(encode,101,i);
    }   
   
    blood=encode[100];
}
 
void end_game(){
    free(encode);
    free(decode);
}
 
void draw (){
   
    Uint32 color;   
    color=SDL_MapRGB(screen->format,0,0,0);
    SDL_FillRect (screen, NULL, color);   
    color = SDL_MapRGB (screen->format, 0xFF, 0, 0);
   
    SDL_Rect *rect=(SDL_Rect *)malloc(sizeof(SDL_Rect));
    rect->w = decode[blood]*5;
    rect->h = 20;
    rect->x = 100;
    rect->y = 100;
    SDL_FillRect (screen, rect, color);
    free(rect);
 
    SDL_Flip (screen);
    SDL_Delay (10);
}
 
 
 
 
int main (int argc, char *argv[]){
    char *msg;
    int done;
   
    SDL_Init (SDL_INIT_VIDEO);
    atexit (SDL_Quit);
 
    screen = SDL_SetVideoMode (640, 480, 16, SDL_SWSURFACE | SDL_DOUBLEBUF);
    SDL_WM_SetCaption ("SDL MultiMedia Application", NULL);
    begin_game();
   
 
    done = 0;
    SDL_Event event;
   
    while (!done){
        SDL_WaitEvent (&event);
        switch (event.type){
            case SDL_KEYDOWN:{
                switch(event.key.keysym.sym){
                    case SDLK_UP:blood = decode[blood]+10>100 ? blood : encode[decode[blood]+10];break;
                    case SDLK_DOWN:blood = decode[blood]-10<0 ? blood : encode[decode[blood]-10];break;
                }
            }
                break;
            case SDL_QUIT:
                done = 1;
                break;
            default:
                break;
        }
        draw ();
    }
   
    end_game();
 
    return 0;
}
 

太阳神上的博客

Happy coding

线性代数学习六，通过初等行变换对矩阵求逆

线性代数学习五，向量的运算与用施密特正交化方法从线性无关组导出正交向量

线性代数学习四，矩阵的运算和求逆

线性代数学习三，将矩阵变为行最简形，标准形以及计算矩阵的秩

线性代数学习二，用克拉默法则求解线性方程组

线性代数学习一，计算行列式

一个算24点的算法

更新的防止游戏修改的算法

防止游戏修改的一个小算法