火狐,你大概知道~
英伟达呢?第一印象会是个沿海服装或者皮鞋厂吧…
Anyway,英特尔之后大家都喜欢给自己起个中文名,尤其是在中国设立研发机构的公司都迫不及待地起个中文名以便与总部划清界限(没错,说的就是谷歌)。
Firefox和Nvidia看起来好像是完全不相干的两个公司嘛。其实不然,总感觉这两个公司的产品现在越来越有着相似的一面。
哗哗哗时间过去三五年当云计算成真,当我们的个人终端已经不需要所谓的主机而变成一个屏幕的时候,当网线和电线早就集成在一起,要上网只要插电源的时候,Google所谓网络操作系统(其实就是Google Chrome或者其他浏览器,比如Firefox)大行其道的时候,当我们的所有东西都运行在说不清楚在什么地方的服务器的时候,Firefox就取代了Nvidia,接下了为用户渲染呈现视觉效果的重任。
我们还是看看现在的JavaScript已经强大到了什么地步吧!

2D

[singlepic=18425]

JavaScript Super Mario Bros.
没错,JavaScript版的马里奥兄弟。也许你还记得,天朝的JavaScript开发者早就推出了网页版仙剑。

[singlepic=18427,600,425]

JSLab Plot Tool
JavaScript版Matlab。

“3D”

[singlepic=18424]

http://processing.org/learning/3d/
3D的JavaScript库

[singlepic=18426]

10款让你震撼的图片展示js代码
Apple Cover Flow效果的JavaScript实现,这似乎已经不算是什么了。

猜一下吧,以下的哪一个会成为几年之后的Nvidia?

The following ones are the new generation JavaScript engines for web browsers, all implementing just-in-time compilation (JIT) or variations of that idea:

我一直觉得孔乙己会做一个很好的HR。
“读过书,……我便考你一考。茴香豆的茴字,怎样写的?” ——孔乙己

在初学一门编程语言的时候,写一个“Hello world!”程序是最常见的入门方法。通过写一个成功的“Hello world!”,可以实践这门语言最基本的语法特性,还可以带给自己成就感,真是一举两得。C/C++语言本身有很多特性,如果能够将这些技术分解出来变成一个个的“Hello world!”,并且将这些技术点到为止,貌似也算是一件善事。这里,列举了10个“Hello world!”程序,大家雅俗共赏一下。

1. 最经典的“Hello world!”

“Hello world!”最经典的写法当然是直接用 printf 输出“Hello world!”这几个字符了。无论用C还是 C++,写起来都非常的简洁明了。这里把最常见的几个全部列在下面。

[code=’c++’]
#include
#include

int main()
{
printf(“Hello world!”); // 教科书的写法
puts(“Hello world!”); // 我最喜欢的
puts(“Hello” ” ” “world!”); // 拼接字符串
std::cout << "Hello world!" << std::endl; // C++风格的教科书写法 return 0; } [/code] 特别需要注意的是,在C/C++里,如果两个字符串之间除空白符以外没有任何东西,编译器会自动认为这两个字符串是连在一起的字符串。这样,如果一个字符串过长,可以用这种方法换行来写,既不浪费性能,又美观。

2. 用宏写的“Hello world!”

在C/C++里,宏是一个神奇的东西。特别是在C语言中,宏可以帮我们做一些“又脏又累”的活,包括拼接代码片断、隐藏繁琐的实现细节等等。其中特别有趣的是“#”的用法,它可以“提取”参数的名字,把它变成字符串。
[code=’c++’]
#include

#define Say(sth) puts(#sth)

int main()
{
return Say(Hello world!);
}
[/code]

请注意,这个Hello world可是完全没有出现引号哦!

3. 断章取义的“Hello world!”

字符串是一种常量这当然毫无疑问,但是它的类型是什么,这就需要考虑一下了。使用C++的typeid就可以这个问题的答案,而且只要是符合C或C++标准的编译器就应该是一样的结果。比如字符串“Hello world!”,它的类型就是 char const [13]。
知道了这个,就可以写出以下的“Hello world!”:
[code=’c++’]
#include

int main()
{
return puts(&”Do not say: Hello world!”[12]);
}
[/code]

4. 退出时运行的“Hello world!”

大家都知道 main 函数退出意味着程序结束,可是这并不完全正确,我们完全可以在 main 函数退出以后做很多事呢——比如说,输出“Hello world!”。这个功能依赖于C标准库中提供的函数 atexit(),调用这个函数并注册自己的回调函数就行。需要注意,这个函数可以调用多次,最后注册的函数最先执行。
[code=’c++’]
#include
#include

void say()
{
printf(“world!”);
}

void sth()
{
printf(“Hello “);
}

int main()
{
return atexit(say), atexit(sth);
}
[/code]

5. 读取自己的“Hello world!”

C/C++的编译器提供了一些有用的内置宏,最常用的就是 __FILE__ 和 __LINE__ 了。其中,__FILE__ 代表当前的源文件的文件名,嗯,对了,如果我们让这个程序读取自己的源文件,不就可以做一个很有意思的“Hello world!”了么?
[code=’c++’]
// Hello world!

#include
#include
#include

int main()
{
std::ifstream ifs(__FILE__);
std::string say, some, word;

ifs >> say >> some >> word;
std::cout << some << " " << word; return 0; } [/code]

6. 话分两头的“Hello world!”

有了C++的类,我们就可以光明正大的在 main 函数执行之前和之后做感兴趣的事情了。我们可以声明一个全局的类的实例,这样,在 main 函数执行之前会调用这个类的构造函数,结束之后则会调用析构函数。
[code=’c++’]
#include

class say
{
public:
say()
{
std::cout << "Hell"; } ~say() { std::cout << "world!"; } }hello; int main() { std::cout << "o "; return 0; } [/code]

7. 传入模板的“Hello world!”

C++的模板功能极为强大,可以说是C++里面最艰深、最经典、最时尚的部分。一个“Hello world!”当然无法使用很多很高级的模板技巧,我也不想只使用模板特化这样无阻挂齿的小技巧,嗯,那就来演示一个比较罕见的用法吧。
[code=’c++’]
#include

template
class say
{
public:
void operator () ()
{
std::cout << words; } }; extern char hello[] = "Hello world!"; int main() { return say()(), 0;
}
[/code]

请注意,这个 extern 是十分必要的,只有加上了 extern,这个指针才是一个编译器间可以确定的值,也才可以参与模板运算。还有,hello 必须为数组类型,而不能为 char*,这个道理和加 extern 是一样的。
此外,这里还演示了 functor 的用法,嗯,关于它的优点就不在这里多说了,反正是与原生指针相比有很多好处就是了。

8. 调用私有函数的“Hello world!”

我们知道,C++类的私有函数是不能被外界访问的,比如说 main 函数里面,它绝对不能访问类的私有函数,除非把它设为类的友元函数。不过我们还是可以用一些比较奇怪的方法访问类的私有函数——当然,这个私有函数必须满足一个条件:它是虚函数。
这里就涉及到一个问题,指向虚函数的虚表放在哪里?对于 VS.Net 2003 而言,虚表是类的第一个成员,虚函数指针按照函数声明的顺序放在虚表里面。当然,这个说法并不严谨,更细节的东西还是去看看那本“成人高钙奶粉”吧,它会给出最权威的解答。
这里是一个很有意思的例子:
[code=’c++’]
#include
#include

class secret
{
private:
virtual void say()
{
std::cout << "Hello world!"; } }; int main() { secret word; (reinterpret_cast(**(intptr_t**)(&word)))();

return 0;
}
[/code]

9. 最暴力的“Hello world!”

最暴力的调用函数的方法是:直接修改函数的返回地址,让这个地址指向我们想要调用的函数。这也就是缓冲区溢出漏洞的应用方法了,不过里面还涉及到很多问题,在这里就不一一列举,想要了解的话,还是去 Google 吧。这里只演示一个可以在 VS.Net 2003 下可以用的“Hello world!”。
[code=’c++’]
#include
#include
#include

void say()
{
puts(“Hello world!”);
exit(0);
}

int main()
{
volatile intptr_t a = 0;
volatile intptr_t * p = &a;

*(p + 2) = (intptr_t)say;
*(p + 3) = (intptr_t)say;

return 0;
}
[/code]

10. 外星人说的“Hello world!”

好了,这个“Hello world!”是最匪夷所思的一个了!不过它并没有涉及任何复杂的C/C++语言特性,只是看起来有点酷。你能看懂外星人在说什么不?
[code=’c++’]
#include

void alien_say(char * p)
{
while (putchar(*(p += *(p + 1) – *p)));
}

int main()
{
return alien_say(“BETHO! Altec oh liryom(a loadjudas!) dowd.”), 0;
}
[/code]

[code=’c#’]
using System;
using System.Collections.Generic;
using System.Text;
using System.Reflection;

namespace ConsoleApplication1
{
public class ReflectionTest
{
public const int test1 = 1;
public readonly static int test2 = 1;
public static int test3 = 1;
public readonly int test4 = 1;
}

class Program
{
static void Main(string[] args)
{
ReflectionTest t = new ReflectionTest();
FieldInfo f;

// const int test1
// const不应该被更改,猜想应当抛出异常
// 运行中SetValue(t, 2);确实抛出System.FieldAccessException异常
Console.WriteLine(“test1=” + ReflectionTest.test1);
f = typeof(ReflectionTest).GetField(“test1”);
f.SetValue(t, 2);
Console.WriteLine(“test1=” + ReflectionTest.test1);

// readonly static int test2
// 因为readonly不进行编译时检查,编译通过,但是执行时应当出错
// 但是实际中没有任何提示,也并未更改,错误被吃掉了!
Console.WriteLine(“test2=” + ReflectionTest.test2);
f = typeof(ReflectionTest).GetField(“test2”);
f.SetValue(t, 2);
Console.WriteLine(“test2=” + ReflectionTest.test2);

// static int test3
// static变量当然可以通过反射更改
Console.WriteLine(“test3=” + ReflectionTest.test3);
f = typeof(ReflectionTest).GetField(“test3”);
f.SetValue(t, 2);
Console.WriteLine(“test3=” + ReflectionTest.test3);

// readonly int test4
// 实例中的readonly变量可以通过反射更改其值
// 因此,readonly变量的赋值方法总共有三种:
// 1. 在声明时对readonly变量赋值;
// 2. 在构造函数中对readonly变量赋值;
// 3. 使用反射在实例生命期中对readonly变量赋值。
Console.WriteLine(“test4=” + t.test4);
f = typeof(ReflectionTest).GetField(“test4”);
f.SetValue(t, 2);
Console.WriteLine(“test4=” + t.test4);
}
}
}
[/code]

运行结果:
[code=’sh’]
test1=1
未处理的异常: System.FieldAccessException: 无法设置常量字段。
在 System.Reflection.MdFieldInfo.SetValue(Object obj, Object value, BindingFlags invokeAttr, Binder binder, CultureIn
fo culture)
在 System.Reflection.FieldInfo.SetValue(Object obj, Object value)
在 ConsoleApplication1.Program.Main(String[] args) 位置 C:\Documents and Settings\Zheng Li\桌面\ConsoleApplication1\C
onsoleApplication1\Program.cs:行号 28
[/code]

注释掉第28行的结果:
[code=’sh’]
test1=1
test1=1
test2=1
test2=1
test3=1
test3=2
test4=1
test4=2
[/code]

用惯C#,比如我想让一个int数等于无穷大,只需要简单写:
[code=’c#’]
int a = int.MaxValue;
[/code]
转到C++上,疑惑了…
首先C++不会有属性这种东西,而且不同平台上的某个类型的最大最小值是不一样的。
解决方案是使用limits头文件的方法。
[code=’cpp’]
#include #include
using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
cout<<"short:"<

广度优先搜索(Breadth-First Search, BFS, 台湾称“横向优先搜寻”)是最简单的图搜索算法之一。广度优先搜索的特点是总是沿已发现与未发现的边界,向外依次扩展。设起始节点为s,则广度优先搜索算法首先会发现与s距离为k的所有结点后,才会发现与s距离为k+1的结点。
广度优先搜索在运行过程中将结点标识为三种状态:

  • 白色:未被发现的结点;
  • 灰色:已被发现,但与其相连的结点尚未全部发现的结点(下一轮进行发现的结点,也是发现结点集的边界);
  • 黑色:已被发现,且与之相连的其他结点也已经发现。

广度优先搜索因为存在单一的起始结点s,因此整个发现过程可以看作是以s为根节点的一棵树,称为广度优先树,广度优先搜索的过程也是建立一棵以s为根的广度优先树的过程。
广度优先树中对每个结点u记录三种信息:

  • π[u]:广度优先树中u的父结点,意味着u第一次被发现时所通过的上一级结点;
  • d[u]:u与根节点s的距离,如果是无权图,也是su的最短距离;
  • color[u]:u结点的颜色。

设图G = (V, E)V是顶点集,E是边集。s是起始节点。
则广度优先搜索(Breadth-First Search, BFS)算法如下:
[code=’c#’]
// 初始化整个图(除去起始结点s)
foreach(Vertex u in V[G] – {s})
{
u.Color = BFSColor.WHITE;
u.D = int.MaxValue;
u.π = null;
}

// 设置起始结点s
s.Color = BFSColor.GRAY;
s.D = 0;
s.π = null;

// 初始化一个队列
Queue q = new Queue();
q.Enqueue(s);
while(q.Count > 0)
{
Vertex u = q.Dequeue();
foreach(Vertex v in u.Neighbors)
{
if(v.Color == BFSColor.WHITE)
{
v.Color = BFSColor.GRAY;
v.D = u.D + 1;
v.π = u;
q.Enqueue(v);
}
}
u.Color = BFSColor.BLACK;
}
[/code]
广度优先搜索(Breadth-First Search, BFS)的算法复杂度是O(V+E),其中O(V)时间用于第一步初始化,O(E)时间用于遍历(因为每个结点的邻接表只会访问一次)。

在计算机科学中我们经常说类似这样的话:
“基于交换的排序算法的时间复杂度至少是O(nlogn)的。”
但是这里从来不说所谓logn,是以几为底数的logn?
实际上,我们有:

[singlepic=18396]

所以在计算机科学中谈论的对数logn,其底数是无所谓的。但是默认情况,如果写成logn,一般认为是以2为底的n的对数。

全周期线性同余随机数生成器(Full period linear congruential random generator):

[singlepic=18395]

其中如果前两项的和为非负数,则δ(Xi)=0,否则δ(Xi)=1。
研究发现取素数M=2147483647,A=48271可以取得不错的随机性。鉴于这样的取值被仔细研究过并广泛应用,因此一般不要改这两个取值。

算法实现

[code=’cpp’]
class RandomFactory
{
public:
RandomFactory();
long LinerCongruentialRandom();
private:
static const long A = 48271;
static const long M = 2147483647;
static const long Q = M / A;
static const long R = M % A;
long lastValue;
};
[/code]

[code=’cpp’]
#include “stdafx.h”
RandomFactory::RandomFactory()
{
this->lastValue = 1;
}

long RandomFactory::LinerCongruentialRandom()
{
long temp = this->A * (this->lastValue % this->Q) –
R * (this->lastValue / this->Q);
if(temp < 0) { temp += this->M;
}
this->lastValue = temp;
return temp % 10;
}
[/code]

测试代码

[code=’cpp’]
RandomFactory *random = new RandomFactory();
int *statistics = new int[10];
for(long i = 0; i < 10; ++i) { statistics[i] = 0; } for(long i = 0; i < 1000; ++i) { int thisRandom = random->LinerCongruentialRandom();
statistics[thisRandom]++;
//cout<<"["<计算结果

[code=’sh’]
[0]:94
[1]:114
[2]:105
[3]:90
[4]:98
[5]:101
[6]:91
[7]:105
[8]:91
[9]:111
[/code]

我们还是可以发现不错的随机性。