公式：f(0) = 0, f(1) = 1, f(2)=1, f(n)=f(n-1)+f(n-2)
递归
int fibona(int n)
{
if(n==0)
retrurn 0;
if(n==1 || n==2)
return 1;
return fibona(n-1)+fibona(n-2);
}非递归
int fibona(int n)
{
if(n==0)
retrurn 0;
if(n==1 || n==2)
return 1;
int a = 1;
int b = 1;
int num = 0;
for(int i=3;i<=n;i++)
{
num = a+b;
a = b;
b=num;
}
return num;
}cocos2d-html5（以下简称ch5）是一款用javascript和html5实现的，基于cocos2d-x的游戏引擎，相对于另外一款以javascript编写的游戏引擎，
cocos2d-js,ch5具有体积小，结构简单的优点，特别适合各种Web小游戏的开发，尤其是当下很火爆的微信社交小游戏，我将以一款简单的拼图游戏为例子，介绍一下如何从零开始快速使用ch5开发游戏。
首先看一下目录结构：
这里的app.js是我们的主要js文件，WeixinApi.js是微信的官方APIJS，如果要接入微信的朋友圈分享功能需要用到这个文件，index.html文件是主要
的展示文件，其作用只是提供一个canvas标签以及引入需要的js文件，res目录则是存放游戏用到的各种图片资源。cocos2d-js-v3.1-lite.js则是cocos2d-html5的库文件，我们需要用到的所有api都被压缩到了这个js文件里面，体积小，便于快速加载。目录大概就是这么多，我们需要编写的逻辑都在app.js里面了，当然这个文件你也可以自己命名，只要在html文件中引入就行。
介绍完了目录结构，我们再看看对于一个游戏开发的小白来说，开发一个简单的ch5游戏，我们需要知道哪些知识。
1、Scenes 场景
就是指游戏运行的背景和总体环境，可以是一张简单的背景图片，也可以是多个图片叠加形成的复杂图形。一个游戏可以有多个不同的场景，但是在游戏运行的某一个特定时刻，场景是不变的。
2、Director 导演
导演是指游戏中负责变换和初始化产后场景的元素，相当于整个游戏中的舞台设计师。
3、Layers 层
层的概念可以理解为场景的组成元素，他是精灵的直接载体，多个层的叠加就可以组成我们需要的游戏效果。
4、sprites 精灵
精灵是整个游戏中的基本单元，同时是一个资源对象，可以进行各种动画动作，如旋转、移动、放大等等，我们看到的游戏效果，大部分都是通过精灵来实现的。
以上就是整个ch5游戏中主要的元素，一个完整的游戏应该包括以上每个元素。
游戏的截图如下：
游戏资源文件共有10个，一个背景图片组成一个场景，9个小图片就是精灵，而9个小图片又一起组成一个层，叠加在背景层之上，通过导演来调用9个精灵元素的相互交换和移动，完成游戏。
具体的代码分析如下：
var PieceSprite = cc.Sprite.extend({
id:0,
_touchBegan: false,
_touchEnabled: true,
beginX:0,
beginY:0,
ctor: function (image,id) {
this._super();
this.init(image);
this.id=id;
},
onEnter: function () {
//cc.Director.getInstance().getTouchDispatcher()._addTargetedDelegate(this, 0);
this._super();
cc.eventManager.addListener({
event: cc.EventListener.TOUCH_ONE_BY_ONE,
swallowTouches: true,
onTouchBegan: this.onTouchBegan,
//onTouchMoved: this.onTouchMoved,
onTouchEnded: this.onTouchEnded
//onTouchCancelled: this.onTouchCancelled
}, this);
},
onExit: function () {
//cc.Director.getInstance().getTouchDispatcher()._removeDelegate(this);
//当Sprite退出后，取消点击事件的注册。
this._touchEnabled = false;
this._super();
},
onTouchBegan: function (touch, event) {
//console.log(touch.getLocation());
//console.log(this);
if (cc.rectContainsPoint(this._node._getBoundingBoxToCurrentNode(), touch.getLocation())) {
//当点击在 Sprite 范围内时，执行。
//在这里处理点击事件。
this._touchBegan = true;
//this.beginX= touch._prevPoint.x;
//this.beginY= touch._prevPoint.y;
this.beginX= touch.getLocation().x;
this.beginY= touch.getLocation().y;
return true; //返回true， 才会执行 onTouchEnded方法。
}
return false;
},
onTouchEnded: function (touch, event) {
if (touch._point.x - this.beginX > 20) {
//this.rightCombineNumber();
//console.log("right");
//alert("right");
doAction("right",this._node.id);
}
else if (touch._point.x - this.beginX < -20) {
//this.leftCombineNumber();
//console.log("left");
//alert("left");
doAction("left",this._node.id);
}
else if (touch._point.y - this.beginY > 20) {
//this.upCombineNumber();
//console.log("up");
//alert("up");
doAction("up",this._node.id);
}
else if (touch._point.y - this.beginY < -20) {
//console.log("down");
//alert("down");
doAction("down",this._node.id);
}
else{
alert(this.beginX);
//alert(touch._point.x);
alert(touch.getLocation().x);
alert(this.beginY);
//alert(touch._point.y);
alert(touch.getLocation().y);
}
if (this._touchBegan) {
this._touchBegan = false;
}
}
});
以上是精灵类的封装，主要定义了具体的动作。
var MyScene = cc.Scene.extend({
cat:null,
touchbeginpos:null,
onEnter:function () {
this._super();
var size = cc.director.getWinSize();
//Manager.init(this);
var scoreLabel = new cc.LabelTTF("0", "黑体", 24, cc.size(150, 30), cc.TEXT_ALIGNMENT_LEFT);
this.addChild(scoreLabel);
scoreLabel.attr({
x:30,
y:cc.director.getVisibleSize().height - 25,
strokeStyle: cc.color(0,0,0),
lineWidth: 2,
color: cc.color(255,150,100),
anchorX:0.1
});
var BgLayer = new BackgroundLayer();
this.addChild(BgLayer);
var playLayer = new PlayLayer();
this.addChild(playLayer);
cc.eventManager.addListener({
event:cc.EventListener.TOUCH_ONE_BY_ONE,
swallowTouches:true,
onTouchMoved:function(touch, event){
},
onTouchEnded:function(touch, event)
{
},
onTouchBegan:function(touch, event)
{
return true;
}
},this);
if(mTimeLayer==null){
mTimeLayer = new TimeLayer();
}
mTimeLayer.setLabel(60);
this.addChild(mTimeLayer);
if(mTimeLayer.isRunning==false){
mTimeLayer.run();
}
}
});这个是场景的初始化，通过多个层进行叠加。
//背景图
var BackgroundLayer = cc.Layer.extend({
ctor:function () {
this._super();
this.init();
},
init:function () {
this._super();
var winsize = cc.director.getWinSize();
//create the background image and position it at the center of screen
var centerPos = cc.p(winsize.width / 2, winsize.height / 2);
var spriteBG = new cc.Sprite("res/bg.png");
//console.log(spriteBG);
spriteBG.setPosition(centerPos);
this.addChild(spriteBG);
}
});这个是一个简单的背景层。
以上就是ch5游戏开发中的主要几个类和函数，基于这些，我们可以开发一些简答的小游戏。
ps:
关于如何初始化拼图游戏中的图片位置的问题，即如何摆放各个小图片的位置，从而保证拼图是可以有解的？对于简单的拼图游戏来说，我们可以先将场景排成正确的位置，然后将空白块和周围相邻的其他方块进行多次的随机交换，这个过程本身就是模仿玩家的移动，所以，它肯定是可逆的，因此总是能保证有解。
给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。
由于所有的数字都是1-n之间，而且只存在一个重复数字，如果没有重复数，那么刚好就是n个数字，mid = (0+n-1)/2，遍历一遍数组，计算小于等于mid的值的个数，
如果没有重复数，小于等于mid的数字刚好是mid个(1,2,...mid)，如果个数大于mid，说明在（1，mid）之间，存在重复的数字；反之，如果个数小于等于mid，说明（mid+1,n）之间，
存在重复的数字；
示例 1:
arr = [1,3,4,2,2]
mid = (0 + 4) / 2 = 2 arr小于等于的2有3个（1，2，2），所以小于mid（2）的1-2中，肯定有重复的值，
high = mid=2，low = 0
mid = (0 + 2) / 2 = 1 arr小于等于的1有1个(1)，2到2中肯定有重复的值
low=mid+1=2，hight=2，不满足while条件，所以这个重复值就是2
所以重复的数是 2
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int low = 0;
int high = nums.size() -1;
while(low < high)
{
int mid = (low+high) / 2;
int count = 0;
for(size_t i=0;i<nums.size();i++)
{
if(nums[i] <= mid)
{
count += 1;
}
}
if(count <= mid)
low = mid+1;
else
high = mid;
}
return low;
}
};1、整个数组分为两部分，第一部分是一个大顶堆，第二部分是一个小顶堆；
2、在插入的过程中，保证第一部分和第二部分的数量相差不超过1，且大顶堆的最大值不超过小顶堆的最小值；
3、优先插入大顶堆，当数量大于小顶堆的时候，把大顶堆的最大值向小顶堆转移；注意，大顶堆只有一个数组的时候，不要转移；
4、当两个堆数量相等的时候，如果大顶堆的最大值大于小顶堆的最小值，那么交换，并重新调整堆；
class MedianFinder {
public:
/** initialize your data structure here. */
std::vector<int> minHeap;
std::vector<int> maxHeap;
MedianFinder() {
minHeap.clear();
maxHeap.clear();
}
void adjustMaxHeap(std::vector<int>& maxHeap,int currentIndex)
{
int parentIndex = findParentNodeIndex(currentIndex);
if(parentIndex < 0 || parentIndex >= maxHeap.size())
{
return;
}
if(maxHeap[parentIndex] < maxHeap[currentIndex])
{
int temp = maxHeap[parentIndex];
maxHeap[parentIndex] = maxHeap[currentIndex];
maxHeap[currentIndex] = temp;
adjustMaxHeap(maxHeap,parentIndex);
}
}
void adjustMaxHeapFromTop(std::vector<int>& heap, int currentIndex)
{
if (currentIndex >= heap.size() || currentIndex < 0)
{
return;
}
// 取左孩子
int iLeftIndex = findLeftNodeIndex(currentIndex);
if (iLeftIndex >= heap.size() || iLeftIndex < 0)
{
return;
}
if (heap[currentIndex] < heap[iLeftIndex])
{
int temp = heap[currentIndex];
heap[currentIndex] = heap[iLeftIndex];
heap[iLeftIndex] = temp;
adjustMaxHeapFromTop(heap, iLeftIndex);
}
// 取右节点
int iRightIndex = findRightNodeIndex(currentIndex);
if (iRightIndex >= heap.size() || iRightIndex < 0)
{
return;
}
if (heap[currentIndex] < heap[iRightIndex])
{
int temp = heap[currentIndex];
heap[currentIndex] = heap[iRightIndex];
heap[iRightIndex] = temp;
adjustMaxHeapFromTop(heap, iRightIndex);
}
}
void adjustMinHeapFromTop(std::vector<int>& heap,int currentIndex)
{
if(currentIndex >= heap.size() || currentIndex < 0)
{
return;
}
// 取左孩子
int iLeftIndex = findLeftNodeIndex(currentIndex);
if(iLeftIndex >= heap.size() || iLeftIndex < 0)
{
return;
}
if(heap[currentIndex] > heap[iLeftIndex])
{
int temp = heap[currentIndex];
heap[currentIndex] = heap[iLeftIndex];
heap[iLeftIndex] = temp;
adjustMinHeapFromTop(heap,iLeftIndex);
}
// 取右节点
int iRightIndex = findRightNodeIndex(currentIndex);
if(iRightIndex >= heap.size() || iRightIndex < 0)
{
return;
}
if(heap[currentIndex] > heap[iRightIndex])
{
int temp = heap[currentIndex];
heap[currentIndex] = heap[iRightIndex];
heap[iRightIndex] = temp;
adjustMinHeapFromTop(heap,iRightIndex);
}
}
int findParentNodeIndex(int index)
{
return floor((index -1 )/2);
}
int findLeftNodeIndex(int index)
{
return 2*index+1;
}
int findRightNodeIndex(int index)
{
return 2*index+2;
}
void adjustMinHeap(std::vector<int>& minHeap,int currentIndex)
{
// 1、找到父节点
int parentIndex = findParentNodeIndex(currentIndex);
if(parentIndex < 0)
{
return;
}
if(minHeap[parentIndex] > minHeap[currentIndex])
{
int temp = minHeap[parentIndex];
minHeap[parentIndex] = minHeap[currentIndex];
minHeap[currentIndex] = temp;
adjustMinHeap(minHeap,parentIndex);
}
}
void addNum2MaxHeap(int num)
{
maxHeap.push_back(num);
adjustMaxHeap(maxHeap,maxHeap.size()-1);
if ((maxHeap.size() > minHeap.size()) && maxHeap.size() > 1)
{
int max = maxHeap[0];
addNum2MinHeap(max);
maxHeap[0] = maxHeap[maxHeap.size()-1];
maxHeap.pop_back();
adjustMaxHeapFromTop(maxHeap,0);
}
if ((maxHeap.size() == minHeap.size()) && maxHeap.size() >= 1)
{
if (maxHeap[0] > minHeap[0])
{
int tmp1 = maxHeap[0];
int tmp2 = minHeap[0];
maxHeap[0] = tmp2;
adjustMaxHeapFromTop(maxHeap, 0);
minHeap[0] = tmp1;
adjustMinHeapFromTop(minHeap, 0);
}
}
}
void addNum2MinHeap(int num)
{
minHeap.push_back(num);
adjustMinHeap(minHeap,minHeap.size()-1);
}
void addNum(int num) {
addNum2MaxHeap(num);
}
double findMedian() {
if((minHeap.size() + maxHeap.size()) % 2 == 0)
{
double t = (double)minHeap[0] + (double)maxHeap[0];
return t /2;
}
if(minHeap.size() > maxHeap.size() )
{
return minHeap[0];
}
return maxHeap[0];
}
};
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder* obj = new MedianFinder();
* obj->addNum(num);
* double param_2 = obj->findMedian();
*/