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個頻帶