n星算法思路
1. Floyd算法的核心思路
通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。
从图的带权邻接矩阵A=[a(i,j)] n×n开始，递归地进行n次更新，即由矩阵D(0)=A，按一个公式，构造出矩阵D(1)；又用同样地公式由D(1)构造出D(2)；……；最后又用同样的公式由D(n-1)构造出矩阵D(n)。矩阵D(n)的i行j列元素便是i号顶点到j号顶点的最短路径长度，称D(n)为图的距离矩阵，同时还可引入一个后继节点矩阵path来记录两点间的最短路径。
采用松弛技术（松弛操作），对在i和j之间的所有其他点进行一次松弛。所以时间复杂度为O(n^3); 其状态转移方程如下： map[i,j]:=min{map[i,k]+map[k,j],map[i,j]}；
map[i,j]表示i到j的最短距离，K是穷举i,j的断点，map[n,n]初值应该为0，或者按照题目意思来做。
当然，如果这条路没有通的话，还必须特殊处理，比如没有map[i,k]这条路。
2. 深度优先搜索和广度优先搜索、A星算法三种算法的区别和联系
在说它之前先提提状态空间搜索。状态空间搜索，如果按专业点的说法就是将问题求解过程表现为从初始状态到目标状态寻找这个路径的过程。通俗点说，就是 在解一个问题时，找到一条解题的过程可以从求解的开始到问题的结果（好象并不通俗哦）。由于求解问题的过程中分枝有很多，主要是求解过程中求解条件的不确 定性，不完备性造成的，使得求解的路径很多这就构成了一个图，我们说这个图就是状态空间。问题的求解实际上就是在这个图中找到一条路径可以从开始到结果。 这个寻找的过程就是状态空间搜索。 常用的状态空间搜索有深度优先和广度优先。广度优先是从初始状态一层一层向下找，直到找到目标为止。深度优先是按照一定的顺序前查找完一个分支，再查找另一个分支，以至找到目标为止。这两种算法在数据结构书中都有描述，可以参看这些书得到更详细的解释。 前面说的广度和深度优先搜索有一个很大的缺陷就是他们都是在一个给定的状态空间中穷举。这在状态空间不大的情况下是很合适的算法，可是当状态空间十分大，且不预测的情况下就不可取了。他的效率实在太低，甚至不可完成。在这里就要用到启发式搜索了。 启发中的估价是用估价函数表示的，如： f(n) = g(n) + h(n) 其中f(n) 是节点n的估价函数，g(n)实在状态空间中从初始节点到n节点的实际代价，h(n)是从n到目标节点最佳路径的估计代价。在这里主要是h(n)体现了搜 索的启发信息，因为g(n)是已知的。如果说详细点，g(n)代表了搜索的广度的优先趋势。但是当h(n) >> g(n)时，可以省略g(n)，而提高效率。这些就深了，不懂也不影响啦！我们继续看看何谓A*算法。 2、初识A*算法 启发式搜索其实有很多的算法，比如：局部择优搜索法、最好优先搜索法等等。当然A*也是。这些算法都使用了启发函数，但在具体的选取最佳搜索节点时的 策略不同。象局部择优搜索法，就是在搜索的过程中选取“最佳节点”后舍弃其他的兄弟节点，父亲节点，而一直得搜索下去。这种搜索的结果很明显，由于舍弃了 其他的节点，可能也把最好的节点都舍弃了，因为求解的最佳节点只是在该阶段的最佳并不一定是全局的最佳。最好优先就聪明多了，他在搜索时，便没有舍弃节点 （除非该节点是死节点），在每一步的估价中都把当前的节点和以前的节点的估价值比较得到一个“最佳的节点”。这样可以有效的防止“最佳节点”的丢失。那么 A*算法又是一种什么样的算法呢？其实A*算法也是一种最好优先的算法。只不过要加上一些约束条件罢了。由于在一些问题求解时，我们希望能够求解出状态空 间搜索的最短路径，也就是用最快的方法求解问题，A*就是干这种事情的！我们先下个定义，如果一个估价函数可以找出最短的路径，我们称之为可采纳性。A* 算法是一个可采纳的最好优先算法。A*算法的估价函数可表示为： f'(n) = g'(n) + h'(n) 这里，f'(n)是估价函数，g'(n)是起点到终点的最短路径值，h'(n)是n到目标的最断路经的启发值。由于这个f'(n)其实是无法预先知道 的，所以我们用前面的估价函数f(n)做近似。g(n)代替g'(n)，但 g(n)>=g'(n)才可（大多数情况下都是满足的，可以不用考虑），h(n)代替h'(n)，但h(n)<=h'(n)才可（这一点特别 的重要）。可以证明应用这样的估价函数是可以找到最短路径的，也就是可采纳的。我们说应用这种估价函数的最好优先算法就是A*算法。哈。你懂了吗？肯定没 懂。接着看。 举一个例子，其实广度优先算法就是A*算法的特例。其中g(n)是节点所在的层数，h(n)=0，这种h(n)肯定小于h'(n)，所以由前述可知广度优先算法是一种可采纳的。实际也是。当然它是一种最臭的A*算法。 再说一个问题，就是有关h(n)启发函数的信息性。h(n)的信息性通俗点说其实就是在估计一个节点的值时的约束条件，如果信息越多或约束条件越多则排除 的节点就越多，估价函数越好或说这个算法越好。这就是为什么广度优先算法的那么臭的原因了，谁叫它的h(n)=0，一点启发信息都没有。但在游戏开发中由 于实时性的问题，h(n)的信息越多，它的计算量就越大，耗费的时间就越多。就应该适当的减小h(n)的信息，即减小约束条件。但算法的准确性就差了，这 里就有一个平衡的问题。可难了，这就看你的了！ 好了我的话也说得差不多了，我想你肯定是一头的雾水了，其实这是写给懂A*算法的同志看的。哈哈。你还是找一本人工智能的书仔细看看吧！我这几百字是不足以将A*算法讲清楚的。只是起到抛砖引玉的作用希望大家热情参与吗。
3. 算法题。。
//这是我提交的代码，仅供参考
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
structNode
{
intX;
intY;
intY_tmp;
intl;
intr;
intcapacity;
}node[100001];
intN,R;
intcmp(structNode*a,structNode*b)
{
returna->r-b->r;
}
intIs_Sucess(intmiddle)
{
inti,j,start=0;
for(i=0;i<N;i++)
{
node[i].capacity=middle;
j=start;
while(node[i].capacity>0&&node[j].l<=node[i].X&&j<N)
{
/* if(node[j].Y_tmp==0)
{
j++;
continue;
}*/
if(node[j].r<node[i].X&&node[j].Y_tmp>0)
return0;
if(node[j].l<=node[i].X&&node[j].r>=node[i].X)
{
if(node[i].capacity>=node[j].Y_tmp)
{
node[i].capacity-=node[j].Y_tmp;
node[j].Y_tmp=0;
start=j+1;
}
else
{
node[j].Y_tmp-=node[i].capacity;
node[i].capacity=0;
}
}
j++;
}
}
if(node[N-1].Y_tmp>0)
return0;
return1;
}
intBinary_Search(inthigh,intlow)
{
inti,middle;
while(high!=low)
{
middle=(high+low)/2;
for(i=0;i<N;i++)
node[i].Y_tmp=node[i].Y;
if(Is_Sucess(middle))
high=middle;
else
low=middle+1;
}
returnhigh;
}
intmain()
{
intT;
inti,j;
inthigh;
longlongintlow;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&N,&R);
low=0;
high=0;
for(i=0;i<N;i++)
{
scanf("%d%d",&node[i].X,&node[i].Y);
node[i].l=node[i].X-R;
node[i].r=node[i].X+R;
if(high<node[i].Y)
high=node[i].Y;
low+=node[i].Y;
}
qsort(node,N,sizeof(node[0]),cmp);
low=low/N;
high=Binary_Search(high,low);
printf("%d ",high);
}
system("pause");
return0;
}
4. 深度优先搜索和广度优先搜索、A星算法三种算法的区别和联系
深度优先搜索(又名回溯)建立简单图的生成树的过程本质是递归.宽(广)度优先搜索与深度优先搜索复杂度都为O(e)或者说是O(n的平方).其中n为顶点数,e为边数.
5. 数独算法思路
数独(数和)（英：Cross Sums；日：カックロ）是一种数学智力游戏。数和把填字游戏和数独巧妙地结合在一起，采用填字游戏式的棋盘，解题时在空格中填上1-9的数字。这种游戏不仅需要逻辑思维能力，还需要一点加法运算。
电脑自动生成数独游戏的谜题
要得出所有满足条件的组合确实不是件容易的事情（主要是很多，打印起来很慢） 。但偶们的目标只是每次能得到一个新的组合，然后从格子里面随机遮掉一些数字就可以了。所以只需要在解数独游戏算法的基础上稍作修改即可。
所以，算法的步骤是：
1.往第一行或第一列随机填1-9的数字
2.调用解数独算法得到一个结果
3.每行随机遮掉1-8个数字。如果需要较大的难度，也可以将1-8改为2-8或3-8，等等。
以下是console工程的代码：
// sudoku.cpp : 定义控制台应用程序的入口点。
// by superarhow([email protected])
#include "stdafx.h"
#include "conio.h"
#define SUCCESS 1
#define _FAILED 0
/* 地图类型9*9的char，每个char从0-9，0表示待填 */
typedef char MAPTYPE[9][9];
/* 行数据，同时用作“可能性”数据。如LINETYPE a; 当a[0]为真时表示
当前位置可填1，a[1]为真时表示可填2，以此类推 */
typedef char LINETYPE[9];
typedef void (*ONMAPOKCALLBACK)(MAPTYPE map);
/* 打印地图 */
void mp_map(MAPTYPE dest)
{
for ( int j = 0; j < 9; j++ )
{
for ( int i = 0; i < 9; i++ )
{
printf("%d ", dest[i][j]);
}
printf("\n");
}
printf("\n");
}
int fill_line(MAPTYPE dest, int line, ONMAPOKCALLBACK callback);
/* 填下一个格子。本行的可能性已在调用前算好，要考虑的是列的可能性和九宫格的可能性 */
/* nums_possible : array (0-8) means possible of number (1-9) */
int fill_pos(MAPTYPE dest, LINETYPE nums_possible, int line, int pos, ONMAPOKCALLBACK callback)
{
if ( pos >= 9 )
{
return fill_line(dest, line + 1, callback);
}
if ( dest[pos][line] != 0 ) return fill_pos(dest, nums_possible, line, pos + 1, callback);
for ( int i = 0; i < 9; i++ )
{
if ( !nums_possible[i] ) continue;
/* 检查本列是否重复 */
int vetical_failed = 0;
for ( int j = 0; j < 9; j++ )
if ( dest[pos][j] == i + 1 )
{
vetical_failed = 1;
break;
}
if ( vetical_failed ) continue;
/* 检查九宫格是否重复 */
int nine_failed = 0;
int m = pos / 3;
int n = line / 3;
m *= 3;
n *= 3;
for ( int y = n; y < n + 3; y++ )
{
for ( int x = m; x < m + 3; x++ )
{
if ( dest[x][y] == i + 1 )
{
nine_failed = 1;
break;
}
}
if ( nine_failed ) break;
}
if ( nine_failed ) continue;
/* all ok, try next position */
dest[pos][line] = i + 1;
nums_possible[i] = 0;
if ( fill_pos(dest, nums_possible, line, pos + 1, callback) )
{
/* 本行已全部OK，尝试下一行 */
if ( fill_line(dest, line + 1, callback) ) return SUCCESS;
/* 下一行失败，重新尝试本位置的剩余可能性 */
}
nums_possible[i] = 1;
dest[pos][line] = 0;
}
return _FAILED;
}
/* 填下一行 */
int fill_line(MAPTYPE dest, int line, ONMAPOKCALLBACK callback)
{
if ( line >= 9 )
{
/* map */
callback(dest);
return SUCCESS;
}
LINETYPE nums;
LINETYPE saveline;
/* calc possibility(for the current line) */
for ( int i = 0; i < 9; i++ ) nums[i] = 1; /* all can be */
for ( int i = 0; i < 9; i++ )
{
char n = dest[i][line];
/* save line */
saveline[i] = dest[i][line];
if ( n != 0 ) nums[n - 1] = 0; /* appears */
}
if ( !fill_pos(dest, nums, line, 0, callback) )
{
/* restore line */
for ( int i = 0; i < 9; i++ ) dest[i][line] = saveline[i];
return _FAILED;
}
return SUCCESS;
}
MAPTYPE g_result;
void on_map_ok(MAPTYPE map)
{
memcpy(g_result, map, sizeof(MAPTYPE));
}
#include "windows.h"
int _tmain(int argc, _TCHAR* argv[])
{
MAPTYPE dest;
memset(dest, 0, sizeof(MAPTYPE));
srand( GetTickCount() );
/* 随机填充第一行 */
char ch[9] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
for ( int i = 0; i < 9; i++ )
{
int p = rand() % 9;
char t = ch[p];
ch[p] = ch[i];
ch[i] = t;
}
for ( int i = 0; i < 9; i++ ) dest[i][0] = ch[i];
if ( fill_line(dest, 0, on_map_ok) )
{
/* 修剪掉一些块 */
for ( int i = 0; i < 9; i++ )
{
/* 调整n的取值范围可改变难度 %6 + 3是比较难的 */
int n = (rand() % 6) + 3;
for ( int j = 0; j < 9; j++ ) ch[j] = j; /* ch: index to erase */
for ( int j = 0; j < 9; j++ )
{
int p = rand() % 9;
char t = ch[p];
ch[p] = ch[i];
ch[i] = t;
}
for ( int j = 0; j < n; j++ ) g_result[ch[j]][i] = 0;
}
mp_map(g_result);
}
getch();
return 0;
}
看完这些，你对数独的算法了解了吗？
6. 利用选择法，描述将 N 个数按从小到大顺序排列的基本思路与算法流程。
把未排序的数放在右边，已排序的放左边，算法就是，不断地从右边选取最小者放到左边。
选择排序法是一种不稳定的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完。
选择排序法的第一层循环从起始元素开始选到倒数第二个元素，主要是在每次进入的第二层循环之前，将外层循环的下标赋值给临时变量。
接下来的第二层循环中，如果发现有比这个最小位置处的元素更小的元素，则将那个更小的元素的下标赋给临时变量，最后，在二层循环退出后，如果临时变量改变，则说明，有比当前外层循环位置更小的元素，需要将这两个元素交换。
(6)n星算法思路扩展阅读：
选择法的稳定性
选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，直到第n-1个元素，第n个元素不用选择了，因为只剩下它一个最大的元素了。
那么，在一趟选择，如果一个元素比当前元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。
比较拗口，举例如下，序列5、8、5、2、9，知道第一遍选择第1个元素5会和2交换，那么原序列中两个5的相对前后顺序就被破坏了，所以选择排序是一个不稳定的排序算法。
7. 征求n阶乘的优化算法
这是被我初学时写的如今已我抛弃的"算法", 其实也不是什么算法, 只不过类设计一个, 而且类的实现还没有完善, 因为写到一半发现我的构思有多么垃圾我就没再写下去了, 支持4294967295位有符号和无符号整数, 你可以把UBI_SIGNED给undef了对于无符号整型可能要快一点, 我也没算过100000!有没有超过这个范围, 你要算的话自己去算下看看, 我没那个时间.
UBI意为unbounded integer
忘了说你可以去这个网站看下一个专门为理论上的"无限大"数做的的C++库:
http://www.apfloat.org/apfloat/
apfloat的意思是arbitrary precision float, 这个人写的算法很吊, 只能这样说, 2.6亿位的π只用几乎1秒多就出来了, 算100W!也不在话下, 用的大约是数论变换, 你要算法的话可以去参考下, 另:
其实the art of computer programming vol2 siminumerical algorithm有很多关于这方面的介绍的, 我曾经瞥过几眼, 但由于本人数学太烂, 看懂几乎是 impossible -_-~~. 所以也只好作罢...
我写这个烂代码计算乘法很"慢", 但计算加法还马虎, 我曾经用跌代法算Fibonacci的第10W项貌似也只用了很短的时间(感觉不长, 具体记不得了).
计算了一个1000!, 3秒左右:
1239862902
9445909974
1418278094
5573543251
2912073791
0878297308
8932076716
3650241536
0821333186
4516076535
6153071277
8114194545
3408243920
9880051954
5832036786
6848259012
3448259932
8558600301
2188525247
4228458623
5904339901
0164192106
0241866493
1399694290
986355
8633969099
2154399457
8184009699
0277534720
0000000000
0000000000
0000000000
00000000
代码:
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <stdexcept>
using namespace std;
#define UBI_SIGNED
class UBI
{
typedef unsigned char byte;
typedef signed char diff_byte;
typedef vector<byte> mem_type;
typedef mem_type::size_type size_type;
#define SMALL(result) result.first
#define BIG(result) result.second
typedef pair<const UBI*, const UBI*> cmp_result;
static inline byte HiByte(byte b)
{
return b >> 4;
}
static inline byte LoByte(byte b)
{
return b & 0xF;
}
static inline byte MakeByte(byte a, byte b)
{
return (a << 4) | (b & 0xF);
}
void Init(string str);
short Strcmp(const string& lhs, const string& rhs)const;
cmp_result UBICmp(const UBI& lhs, const UBI& rhs)const;
#ifndef UBI_SIGNED
void CheckVal(const string& str)const
{
if(str[0] == '-')
throw domain_error
("Try to initial or assign an negtive value" \
"to a number that is positive.");
}
#endif
public:
UBI(size_type digit = 20);
UBI(const char* c_str, size_type digit = 20);
UBI(const string& str, size_type digit = 20);
UBI(const UBI& UBI);
UBI operator + (const UBI& rhs)const;
UBI operator - (const UBI& rhs)const;
UBI operator * (const UBI& rhs)const;
UBI operator / (const UBI& rhs)const;
const UBI& operator = (const UBI& rhs);
const UBI& operator += (const UBI& rhs);
const UBI& operator -= (const UBI& rhs);
const UBI& operator *= (const UBI& rhs);
const UBI& operator /= (const UBI& rhs);
string ToString()const;
void clear();
private:
mem_type mem;
#ifdef UBI_SIGNED
bool isSigned;
bool IsSigned()const;
mutable bool mutex;
#endif
};
UBI::UBI(size_type digit)
{
#ifdef UBI_SIGNED
isSigned = false;
mutex = false;
#endif
mem.reserve(digit);
}
void UBI::Init(string str)
{
if(str[0] == '-')
str.erase(0, 1);
int i;
for(i = str.size() - 1; i-1 >= 0; i -= 2)
{
mem.push_back(MakeByte(LoByte(str[i]), LoByte(str[i-1])));
}
if(i == 0)mem.push_back(MakeByte(LoByte(str[0]), 0));
}
short UBI::Strcmp(const string& lhs, const string& rhs)const
{
if(lhs.size() > rhs.size())
return 1;
else if(lhs.size() < rhs.size())
return -1;
else if(lhs > rhs)
return 1;
else if(lhs < rhs)
return -1;
return 0;
}
UBI::cmp_result UBI::UBICmp(const UBI& lhs, const UBI& rhs)const
{
string sLhs(lhs.ToString());
string sRhs(rhs.ToString());
if(Strcmp(sLhs, sRhs) == 0)
return make_pair(&lhs, &lhs);
#ifdef UBI_SIGNED
if(sLhs[0] == '-')sLhs.erase(0, 1);
if(sRhs[0] == '-')sRhs.erase(0, 1);
#endif
const UBI* small =
Strcmp(sLhs, sRhs) == -1 ?
this : &rhs;
const UBI* big =
&rhs == small ?
this : &rhs;
return make_pair(small, big);
}
#ifdef UBI_SIGNED
bool inline UBI::IsSigned()const
{
return isSigned;
}
#endif
UBI::UBI(const char* c_str, size_type digit)
{
#ifdef UBI_SIGNED
isSigned = *c_str == '-' ? true : false;
mutex = false;
#else
CheckVal(string(c_str));
#endif
if(string(c_str).size() > digit)
mem.reserve(string(c_str).size());
else
mem.reserve(digit);
Init(string(c_str));
}
UBI::UBI(const string& str, size_type digit)
{
#ifdef UBI_SIGNED
isSigned = str[0] == '-' ? true : false;
mutex = false;
#else
CheckVal(str);
#endif
if(str.size() > digit)
mem.reserve(str.size());
else
mem.reserve(digit);
Init(str);
}
UBI::UBI(const UBI& UBI) : mem(UBI.mem)
{
#ifdef UBI_SIGNED
isSigned = UBI.isSigned;
mutex = false;
#endif
}
const UBI& UBI::operator = (const UBI& rhs)
{
if(this == &rhs)return *this;
mem.assign(rhs.mem.begin(), rhs.mem.end());
#ifdef UBN_SIGNED
isSigned = rhs.isSigned;
#endif
return *this;
}
UBI UBI::operator + (const UBI& rhs)const
{
if(mem.empty() || mem.size() == 1 && mem[0] == 0x0)
return rhs;
if(rhs.mem.empty() || rhs.mem.size() == 1 && rhs.mem[0] == 0x0)
return *this;
#ifdef UBI_SIGNED
if(!mutex)
{
if(isSigned && !rhs.isSigned || !isSigned && rhs.isSigned)
{
mutex = true;
return *this - rhs;
}
}else
mutex = false;
#endif
cmp_result result(UBICmp(*this, rhs));
byte prevHiRemain = 0;
size_type smallSize = SMALL(result)->mem.size();
UBI tempUBI;
for(size_type i = 0; i < BIG(result)->mem.size(); ++i)
{
byte tempHi =
HiByte(BIG(result)->mem[i]) +
(i < smallSize ? HiByte(SMALL(result)->mem[i]) : 0)
+ prevHiRemain;
byte tempLo =
LoByte(BIG(result)->mem[i]) +
(i < smallSize ? LoByte(SMALL(result)->mem[i]) : 0);
prevHiRemain = 0;
if(tempHi > 9)
{
tempLo += tempHi / 10;
tempHi = tempHi % 10;
}
if(tempLo > 9)
{
prevHiRemain = tempLo / 10;
tempLo = tempLo % 10;
}
tempUBI.mem.push_back(MakeByte(tempHi, tempLo));
}
if(prevHiRemain != 0)
tempUBI.mem.push_back(MakeByte(prevHiRemain, 0));
#ifdef UBI_SIGNED
tempUBI.isSigned = this->isSigned ? true : false;
#endif
return tempUBI;
}
const UBI& UBI::operator += (const UBI& rhs)
{
return *this = *this + rhs;
}
UBI UBI::operator - (const UBI& rhs)const
{
#ifdef UBI_SIGNED
if(!mutex)
{
if(!isSigned && rhs.isSigned || isSigned && !rhs.isSigned)
{
mutex = true;
return *this + rhs;
}
}else
mutex = false;
#endif
cmp_result result(UBICmp(*this, rhs));
if(SMALL(result) == BIG(result))
return UBI("0");
byte prevHiBorrow = 0;
size_type smallSize = SMALL(result)->mem.size();
UBI tempUBI;
for(size_type i = 0; i < BIG(result)->mem.size(); ++i)
{
diff_byte tempHi =
HiByte(BIG(result)->mem[i]) -
(i < smallSize ? HiByte(SMALL(result)->mem[i]) : 0)
- prevHiBorrow;
diff_byte tempLo =
LoByte(BIG(result)->mem[i]) -
(i < smallSize ? LoByte(SMALL(result)->mem[i]) : 0);
prevHiBorrow = 0;
if(tempHi < 0)
{
tempLo -= 1;
tempHi = 10 + tempHi;
}
if(tempLo < 0)
{
prevHiBorrow = 1;
tempLo += 10;
}
tempUBI.mem.push_back(MakeByte(tempHi, tempLo));
}
#ifdef UBI_SIGNED
if(this == BIG(result) && this->isSigned ||
this == SMALL(result) && !this->isSigned)
tempUBI.isSigned = true;
#endif
return tempUBI;
}
UBI UBI::operator * (const UBI& rhs)const
{
if(this->mem[mem.size()-1] == 0 || rhs.mem[rhs.mem.size()-1] == 0)
return UBI("0");
if(this->mem.size() == 1 && this->mem[0] == 0x10)
return rhs;
if(rhs.mem.size() == 1 && rhs.mem[0] == 0x10)
return *this;
cmp_result result(UBICmp(*this, rhs));
UBI tempUBI;
for(size_type i = 0, k = 0; i < SMALL(result)->mem.size(); ++i)
{
byte SmHi = HiByte(SMALL(result)->mem[i]);
byte SmLo = LoByte(SMALL(result)->mem[i]);
byte prevLoRemain = 0;
UBI Hi;
for(size_type j = 0; j < BIG(result)->mem.size(); ++j)
{
byte tempHi = SmHi * HiByte(BIG(result)->mem[j]) + prevLoRemain;
byte tempLo = SmHi * LoByte(BIG(result)->mem[j]);
prevLoRemain = 0;
if(tempHi > 9)
{
tempLo += tempHi / 10;
tempHi %= 10;
}
if(tempLo > 9)
{
prevLoRemain = tempLo / 10;
tempLo %= 10;
}
Hi.mem.push_back(MakeByte(tempHi, tempLo));
}
if(prevLoRemain != 0)
{
Hi.mem.push_back(MakeByte(prevLoRemain, 0));
prevLoRemain = 0;
}
if(k > 0)
{
string _10(Hi.ToString());
_10.resize(_10.size()+k, '0');
Hi = UBI(_10);
}
++k;
tempUBI += Hi;
UBI Lo;
for(size_type j = 0; j < BIG(result)->mem.size(); ++j)
{
byte tempHi = SmLo * HiByte(BIG(result)->mem[j]) + prevLoRemain;
byte tempLo = SmLo * LoByte(BIG(result)->mem[j]);
prevLoRemain = 0;
if(tempHi > 9)
{
tempLo += tempHi / 10;
tempHi %= 10;
}
if(tempLo > 9)
{
prevLoRemain = tempLo / 10;
tempLo %= 10;
}
Lo.mem.push_back(MakeByte(tempHi, tempLo));
}
if(prevLoRemain != 0)
{
Lo.mem.push_back(MakeByte(prevLoRemain, 0));
prevLoRemain = 0;
}
if(k > 0)
{
string _10(Lo.ToString());
_10.resize(_10.size()+k, '0');
Lo = UBI(_10);
}
++k;
tempUBI += Lo;
}
return tempUBI;
}
string UBI::ToString()const
{
if(mem.empty() || mem.size() == 1 && mem[0] == 0)
return string("0");
string temp;
temp.reserve(mem.size()*2);
#ifdef UBI_SIGNED
if(isSigned)
temp.push_back('-');
#endif
int i = mem.size()-1;
while(mem[i] == 0 && i > 0)--i;
for(; i >= 0; --i)
{
temp.push_back(LoByte(mem[i]) + '0');
temp.push_back(HiByte(mem[i]) + '0');
}
unsigned zero = temp.find_first_of("0");
#ifdef UBI_SIGNED
if(zero == 0 || temp[0] == '-' && zero == 1)
temp.erase(zero, 1);
#else
if(zero == 0)
temp.erase(zero, 1);
#endif
return temp;
}
void UBI::clear()
{
#ifdef UBI_SIGNED
isSigned = false;
#endif
mem.clear();
}
template <class T, class U>
T lexical_cast(U u)
{
stringstream sstrm;
sstrm << u;
T t;
sstrm >> t;
return t;
}
int main()
{
UBI a("1");
for(int i = 2; i <= 1000; ++i)
{
a = a * lexical_cast<string>(i);
}
cout << a.ToString();
}
8. 求算法思路：n个数，要在 0 ~ n方减1 的范围内，进行排序，求最优排序方法哎
基数排序。
相当于把这些数转成n进制数，位数只有两位，两趟即可。
%n可以获得个位数，/n可以获得十位数。
9. 求n值的算法分析
这个是传说中的3n+1问题
下界为log（n）
上界至今还无人能解
只是猜想上界是存在的
但无法证明
当n为2的整数幂是有下界
log2(n)
10. wvRN算法的思想
摘要 wvRN算法的思想是，VAD(Voice Activity Detection), 活动语音检测技术在语音信号处理有着重要的作用，如语音增强中估计噪声、语音识别中进行语音端点检测，在语音信号传输中用于非连续传输等等。WEBRTC 中VAD 算法，该算法主要原理是将信号在频谱上进行子带划分为 80~ 250Hz，250~ 500Hz，500Hz~ 1K， 1~ 2K，2~ 3K，3~4KHz ，6个频带