Spring MVC学习遇到的问题：JSP未渲染，直接显示源码

2017年5月31日

汉诺塔QT/C++实现

2016年3月31日

汉诺塔问题十分经典，大家都很熟悉，汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。这次数据结构课程设计要求我们做一个图形化界面的汉诺塔演示程序。

问题分析

为实现汉诺塔图形界面演示，我采用了C++的QT框架，整个程序界面由继承自QWidget的hanoiPanel展示，界面分为四大部分，顶部是菜单栏，用来控制动画运行和调整参数，中部左方为动画主体，右方为使用迭代算法时栈的实时状态动画，下方则为三个文本框，分别显示盘子的移动，递归的参数，和实时代码。

汉诺塔动画主体用QGraphicsView框架展示，每个盘子都是一个QLabel,将其add到QGraphicsScene中，通过QGraphicsView观察，盘子的移动采用QPropertyAnimation动画的方案，而每次盘子移动后的目的坐标，我们定义了一个diskstack类，将柱子看作一个栈，每个diskstack对象可以看作一根柱子，diskstack的成员有柱子的编号（1，2，3），柱子上的盘子数目，一个存放盘子数据disk的栈，一个存放盘子实例QLabel的栈，(我这里将盘子disk和QLabel分离开是为了减少耦合，将盘子的数据（坐标，颜色，长宽）和盘子实例分离开)，每当算法主体盘子移动后，都调用一次diskstack的成员函数upadata_position()以更新实时数据。而栈的动画与此类似。算法主体和各个部分组件的通信(如同步显示汉诺塔移动和栈的出入等)，采用QT的信号槽机制。柱子的数据结构：

#ifndef DISKSTACK_H
#define DISKSTACK_H
#include <QDebug>
#include <QRect>
#include <QStack>
#include <QLabel>

#include "disk.h"

class diskstack
{
    public:
        disk *initial;
        QStack <disk> s_stack;
        int s_height; // Height of the stack = number of disks
        int id;//柱子编号
        QStack<QLabel*> labels;

        void update_position();
        void init(int, int);

};

#endif // DISKSTACK_H

程序截图

汉诺塔2

代码

点此下载：

汉诺塔程序(for windows).zip

汉诺塔代码.zip

或者我的github

阅读全文

斐波那契查找

2015年12月8日

斐波那契数列：

F[0]=0,F[1]=1
F[i]=F[i-1]+F[i-2]

斐波那契查找和二分查找类似，根据斐波那契序列的特点对有序表进行分割。要求开始表中记录的个数为某个斐波那契数小1，即数组个数n=F[k]-1，即数组范围a[0]~a[F[k]-2]，设点mid = F[k-1]-1,则左半部分[0,F[k-1]-2]，右半部分[F[k-1],F[k-2]]。

此时我们可以计算，左半部分长度为F[k-1]-1,右半部分长度为F[k-2]-1。 （右=F[k]-2-(F[k-1]-1)=F[k-1]+F[k-2]-2-(F[k-1]-1)=F[k-2]-1 )

左右都满足F[k]-1的形式，这就是为什么表中记录的个数为某个斐波那契数小1。当原始表不满足时，我们可以将数组A扩展到F[k]-1的长度，不足处用A[n-1]填充，再进行搜索。

所以我们有如下划分，mid是划分点：

当key=a[mid]时，查找成功；
当key < a[mid]时，新的查找范围是第low个到第mid-1个。
当key > a[mid]时，新的查找范围是第mid+1个到第high个。

这些都很好理解，可是mid点怎么表示呢？最初一次划分很容易取得，就是F[k-1]-1（设数组大小为F[k]-1)。因为划分之后左右两边长度也都满足F[k]-1的形式，具体如下：

把划分后的右子数组单独来看，长度为F[K-2]-1,所以mid2到low的距离是F[k-3]-1，（因为当长度是F[k]-1时，mid的值是F[k-1]-1)。
左子数组，同理得mid2到low的距离是F[k-2]-1。（因为左半部分长度为F[k-1]-1）

依次类推。代码如下：

void Fib( int *F)
{
    F[0] = 0;
    F[1] = 1;
    for (int i = 2; i <maxsize ; i++)
    {
        F[i]=F[i-1]+F[i-2];  
    }
}

int FibSearch(int *A,int n,int key)
{
    int *F = new int[maxsize];
    int low = 0, high = n-1;
    Fib(F);
    int k = 0;
    while ( n > F[k]-1 )
        k++;

    int *tmp = new int[F[k]-1];
    for ( int i = 0; i < n; i++)
        tmp[i] = A[i];
    for(int i = n; i < F[k]-1; i++)  
        tmp[i]=A[n-1]; //将数组A扩展到F[k]-1的长度，不足处用A[n-1]填充
    while ( low <= high )
    {
        int mid = low + F[k-1] - 1;
        if ( key < tmp[mid])
        {
            high = mid - 1;
            k -= 1;
        }
        else
        if ( key > tmp[mid])
        {
            low = mid + 1;
            k -= 2;
        }
        else
        {
            if ( mid < n )
                return mid;
            else
                return n - 1;
        }
    }
    delete[] tmp;
    return -1;
}