yichao firstname, zeaster nickname, zhang lastname

2006年10.3云蒙山穿越Trek准备清单Checklist

车头灯
手电筒
军训背带
租绳
塑料袋
雨披
小铁锹

剪子
望远镜
基本药品 创可贴
食品 花生酱、巧克力,压缩饼干
水 男生至少5升,女生至少3升
pda充好电
手套
登山杖
凉鞋
擦汗毛巾
女士带防晒用品,遮阳伞
仿瑞士刀
扑克
火机 火柴
镜子
报纸若干

早7:30在东直门长途客车站集结,坐936到云蒙山公园
沿111国道步行2km到后山铺,开始穿越之旅



没有GPS设备,但可以利用GPS数据
实现GPS数据程序:
输入 点a,N40.60247 E116.78447和点b,N40.60525 E116.77914的坐标信息
输出 b对于a的角度,例如北偏西25度;以及a,b间长度
网上有人说如果不考虑地球的扁平率误差会很大
不过找到了这个网址:
http://www.movable-type.co.uk/scripts/LatLong.html
用这个网页测了
02 N40.60525 E116.77914 途中的岔路,走左边
03 N40.60556 E116.77136 308m 水坝,前方是水泉峪(废墟)
02,02点间距离=0.6577 km
用Google Earth测的距离是0.66 km
看来这个网页还是可以用的,我已经当下来存到手机里了
这样依靠GPS数据,就可以确定下一个点在什么方位,在多少米距离上,迷路以及走弯路的可能就少了

编写一个函数,作用是把一个char组成的字符串循环右移n个

例如,"abcdef"循环右移2个就变为"efabcd"

popo实现了一个,不过需要O(n)的额外空间
程序:
void LoopMove(char * pStr,int steps)
{
int len = strlen(pStr);
char *s = new char[len+1];
int count = 0;
char *temp = pStr;
while (*pStr)
{
s[(count+steps)%len] = *pStr;
pStr++;
count++;
}
s[len] = '\0';
strcpy(temp,s);
delete []s;
}


最近想出了个空间为O(1),时间为O(n)的算法
就是只通过数组指针移动和交换来实现

int LoopMove2(char *p, int i, int t, int s, int m){
int n = strlen(p);
int j = (i+m)%n;
if(t == j) return 0;
p[s] = p[j];
p[j] = p[t];
LoopMove2(p, j, s, t,m);
}

使用方法是
如果要右移2位就调用
LoopMove2(p,0,0,-1,2);

基本思想是:
如果数组X有n个元素,要右移m个位置
申请一个临时变量,设它为数组上的X[-1]
对于数组中的Xi,要把它一次性移到它的最终位置,这个位置是j=(i+m)%n,那么首先把Xj移到X[-1],然后把X[i]移到X[j],接下来一次性移动Xj到它的最终位置(j+m)%n,此时临时变量为X[i],要移动的元素是Xj,并且Xj的值在X[-1]位置上。
由此定义LoopMove2函数,它参数的含义是
i:此步要移动的元素Xi
t:当前元素Xi的值在数组上的位置
s:临时变量在数组上的位置
m:右移的位数

最终移动的终止条件是:
当前元素Xi的值在数组上的位置==Xi要移向的最终位置

这个程序中使用了数组的-1处作为临时变量的位置,主要是想把程序写得简单些
当然这样会带来一些问题,但作为说明性的例子就暂不考虑了。
gmail id: yichao.zhang
欢迎和各位讨论算法

Google 面试第一题解法

Solve this cryptic equation, realizing of course that values for M and E could be interchanged. No leading zeros are allowed.

WWWDOT - GOOGLE = DOTCOM

思路:
穷举法,式子中共有9个不同的字母,数字0-9有10个,因此就从10个数字中任取9个,排成一列,这样分别对应了式子中的字母。
然后判断当前取出的这9个数,是否满足条件。本程序中用check2 函数判断,另外需要考虑WE是可以互换,但不可以相同

答案:只有两组解
777589 - 188103 = 589486
777589 - 188106 = 589483

程序:
Perm1.java
package org.chao.perm;

public class Perm1 {
public static void main(String[] args) {
int size = 9;
int[] a = new int[size];
int all = 10;
check(a,all,size,0);
}

private static void check(int[] a, int all, int size, int depth) {
if(size == depth){
check2(a);
}
for(int i=0; i<all; i++){
int j = 0;
for(;j<depth;j++){
if(a[j] == i){
break;
}
}
if(j==depth && depth<size){
a[depth]=i;
check(a,all, size,depth+1);
}
}
}

private static void check2(int[] a) {
//WWWDOT - GOOGLE = DOTCOM
//w0/6 d1 o2 t3 g4 l5 e6/0 c7 m8
int s1 = a[0]*111000+a[1]*100+a[2]*10+a[3];
int s2 = a[4]*100100+a[2]*11000+a[5]*10+a[6];
int s3 = a[1]*100000+a[2]*10010+a[3]*1000+a[7]*100+a[8];
if(s1-s2 == s3){
System.out.println(s1+" - "+s2+" = "+s3);
}
s1 = a[6]*111000+a[1]*100+a[3]*10+a[4];
s2 = a[4]*100100+a[2]*11000+a[5]*10+a[0];
s3 = a[1]*100000+a[2]*10010+a[3]*1000+a[7]*100+a[8];
if(s1-s2 == s3){
System.out.println(s1+" - "+s2+" = "+s3);
}
}
}


对上面程序的一点改进:
改进部分:如何从10个数字中取出9个排成一列
上面例子中每次递归都要做depth判断来排除已经选用的数字
下面这个程序则不需要判断

程序:
Perm2.java
package org.chao.perm;
public class Perm2 {
public static void main(String[] args) {
int num[] = { 0,1,2,3,4,5,6,7,8,9 };
int n=num.length;
generate(num, n-1);
}
private static void generate(int[] num, int n) {
if (n == 0) {
//打印出num;
} else {
for (int i = 0; i <= n; i++) {
swap(num,i,n-1);
generate(num, n - 1);
swap(num,i,n-1);
}
}
}
private static void swap(int[] num, int i, int j) {
int tmp = num[i];
num[i] = num[j];
num[j] = tmp;
}
}

刚搬家过来,以后就安心在此了

刚从yichao.blog.edu.cn搬家过来
先把以前的日志贴到这里,这也是blog.edu.cn的一个好处,它提供了整站的html格式导出

看图说话,谈谈adapter,proxy,facade,bridge模式的区别与联系

适用人群:对模式有一定了解,但又死扣区别的人。个人意见,仅供参考。

 

adapter_class vs adapter_object

 

适配器模式有两类,一种叫类适配器(adapter_class),另一类是对象适配器(adapter_object)。它俩的区别主要体现在adapter和adaptee的关系上

如果是类继承关系则为adapter_class,如果是对象属性关系,则是adapter_object

如图所示:

 

 

adapter vs proxy

 

适配模式是将一个类的接口转换成客户希望的另外一个接口。

代理模式是为其他对象提供一种代理以控制对这个对象的访问。

这是我们常见到的定义,但是还是让初学者摸不清头脑,adapter和proxy到底有什么区别?

adapter是适配adaptee和target之间的关系,proxy是realSubject对subject的代理。

adaptee和target无关系,realSubject和subject有继承关系。这就是他们的区别。

请看下图:

 

 

facade vs others

 

facade用于为复杂的子系统定义一个新的简单易用的接口。

它的重点在

1 封装复杂的子系统,对外提供一个简单的访问入口。

2 降低外界和子系统的耦合度。加了facade入口,外界就只依赖facade入口,而不用依赖子系统的其他类。

如图所示:

 


 

bridge vs others

 

bridge用于将一个抽象与多个可能的实现连接起来。

它是解决抽象类与其实现类之间依赖关系问题,可以使得抽象和实现各自独立且动态结合。

它使用了composition替代了inheritance,从而解除了抽象类和实现类间的耦合。体现了Favor object composition over class inheritance。

如图所示

 


intel MMX, SSE, SSE2区别与联系

MMX(MultiMediaExtensions) 多媒体增强指令集
实现了单道指令多道数据流(SIMD,single-instruction, multiple-data)的执行模式
支持MMX指令集的处理器有八个64位的寄存器,这个寄存器可以存放的数据类型有四种:字节(byte)、字(word),双字(double-word)
分别可以存放8,4,2个。
举个例子:
支持MMX指令集就是说原来对每个数组中(byte)元素加一的操作现在可以一次性load 8个元素,一次性对这个八个元素加一
这就是所谓的”单道指令多道数据流“
http://blog.csdn.net/guanchanghui/archive/2006/07/28/989256.aspx 上有个很好的演示代码

SSE(Streaming SIMD Extensions)单指令多数据流式扩展
就是扩展了MMX支持的SIMD,支持SSE指令集的处理器有八个128位的寄存器,另外支持的数据类型多了个单精度浮点型

SSE2
就是扩展了的SSE,它的寄存器支持的数据类型比SSE多了个双精度浮点型

除了在多媒体处理方面,在多线程处理方面,也是它们的英雄用武地!

记2006.9.2西北四环路刷

下午的时候感觉浑身发痒,好久没有活动了,前几天还莫名其妙的扭了一下腰,要是不活动活动感觉身体真的锈死了。


 

于是联系好友精灵,一拍即合,我先滑去北航。

考虑到西四环车少,吃过晚饭,3个桃,2个香蕉,于18:40分上路。路上坎坷不平,一点安全感都没有,随时感觉会被绊倒,偶的路滑技术实在是太差了。后来感觉走四环去大运村绕远了,随临时改变方向,从蓝靛厂路向东滑,打算上中关村大街走知春路。

结果就走上了如下图所示的路线,不过这条路倒是小路,车很少,路也很平,滑得很爽,一种流畅的感觉coming

接着沿着那条河,滑到了一座立交桥下,再滑就是农村了,漆黑一片,只好又向西,再上桥逆行,桥上问路,唯有滑下长梯,绕行,终于拐到了顺行的主路上。结果一看路牌,惊讶!我上北四环了,唉,有一次被西北四环这做立交桥打败了!

接着一路无话来到北航,北四环的路还是比西四环要好多了。

在北航校内某路段更是爽啊,尤其以13号宿舍楼以及主m楼前路为代表,听说最近图书馆前,体育馆上的路都相当不错了!哈

在北航,照相后,接着和精灵沿北四环继续滑……

大运动后真不该喝凉水,可我太渴了,后来就小腹疼起来了……

坚持在末班车前滑到653大运村车站,上车会家,到家卸鞋后,感觉脚腕折了……

需要锻炼了 我还计划路滑去天津,这状态可不行啊。加油……

 2006.9.2西北四环路刷