隐约记得之前做过一个c++的题目是判断一个数是否素数（质数） 我当时给的算法是判断 2 - x/2, 因为被除数大于 x/2 那商一定小于2，所以被除数必须大于x/2
最近看书的时候发现通用的算法是计算 2- sqrt(x) 即 根号x 这就让我产生疑问了，毋庸置疑，这个算法的效率更高，时间复杂度是logn。 那为什么到sqrt(x)就够了呢？
我反复思考总算得出了结论，这里用反证法即可：
已知 n 不是素数，且a，b是 n的两个根， a*b = n
假设 b>sqrt(n)，且a>=sqrt(n)
则a*b > sqrt(n) * sqrt(n) 即 a*b > n 与条件相悖
得出若存在一个根大于sqrt(n)，
那必定存在另一个小于sqrt(n)的根
与此对应的逆否命题是
若不存在小于sqrt(n)的根，则不存在大于sqrt(n)的根
根据这个证明的结论，判断是否是素数，最多只需要判断到 n 的平方根即可。
在开发一款中国文化的app时，需要以竖排文字的方式展示诗文。 在CSS中，有一个文字方向的属性可以用来直接显示竖排文字，但是在iOS中并没有直接提供，所以扩展一下String类，可以返回一个竖排多行文字
先看一下效果:
简单做一下说明：
convertVerticalText 是将多行文字转变为多列文字的处理过程，类似于矩阵的对角。
首先获取待转换的文字一共有多少行，那么也就对应着转换后每一行有几个字。
由于每一行的文字个数未必相同，在转换为列的时候，就意味着会有空白，所以要获取最长一行有多少个字符。 每次在取完有效字符后，如果没有达到最长字符时，就要自动填入空白字符了。
// Auto convert text to Vertical text on UILabel
extension UILabel{
func toVertical( gapLength:Int = 1,spaceLength:Int = 1, inverse:Bool = true ){
if self.text != nil{
self.text = self.text!.convertVerticalText(gapLength: gapLength, spaceLength: spaceLength, inverse: inverse)
}
}
}
extension String{
func convertVerticalText( gapLength:Int = 1,spaceLength:Int = 1, inverse:Bool = true ) -> String{
let gap = String.init(repeating: " ", count: gapLength)
let space = String.init(repeating: " ", count: spaceLength)
let sentences = self.split(separator: "\n")
let sequence = 0 ..< sentences.count
var T:[String] = []
var WL:[Int] = []
var maxLength = sentences[0].count
// 统计最长句
for i in sequence {
maxLength = max(maxLength, sentences[i].count)
}
// 初始化
for _ in 0...maxLength-1 {
T.append("")
WL.append(0)
}
for i in sequence {
var idx = 0
for w in sentences[i]{
if w == " "{
T[idx].append( space )
}else{
T[idx].append( w )
}
WL[idx] += 1
if( WL[idx] < sentences.count ){
T[idx].append(gap)
}
idx += 1
}
if idx < maxLength-1{
for sup in idx ... maxLength-1 {
T[sup].append(space)
WL[sup-1] += 1
}
}
}
var _T:String = ""
for single in T {
_T.append( inverse ? String(single.reversed()) : single )
_T.append("\n")
}
return _T
}
}
数据结构、算法与应用 习题6.1 69题 p143
这里应该能支持两种表示法，1链表，2数组。
使用链表比较符合我们直观上对于数字的印象，其中将 rear链接到最后一位数，那么使用prev就可以陆续的取出每一个数字。 并且在进行数学运算时，我们无需关注最终的位数，只需要将结果insert进入结果链表中即可。
由于没有规定一定是正整数，所以需要给一个符号。 （在网上也搜索了一些大数运算的参考，没有提供有符号运算的版本） 带符号的时候，逻辑会变复杂不少。
这里我给出一个带符号的方式 其中isNegative true为负数，false为正数
为了表示符号对于运算的影响，我会写两个版本的 加法
class BigInt: public Chain<int>{
public:
bool isNegative = false;
BigInt( int* a, int size ){ // 基于数组构造
for( int i=0; i<size; i++ ){
insert( a[i] );
}
}
// 最基本的 正正 相加
BigInt& operator+( BigInt& bigInt ){
int plus = 0; // 进位
int res = 0; // 单次计算结果
BigInt result = new BigInt; // 结果
ChainNode<int>* cursor = last();
ChainNode<int>* targetCursor = bigInt.last();
// 使用倒序的方式取出元素并计算
while( cursor->prev() && targetCursor->prev() ){
res = cursor->element + targetCursor->element + plus;
plus = res > 9 ? 1 : 0;
result->prepend( res ); // prepend即为 addAfter( head )
cursor = cursor->prev();
targetCursor = targetCursor->prev();
}
while( cursor->prev() ){
result->prepend( cursor->element );
cursor = cursor->prev();
}
while( targetCursor->prev() ){
result->prepend( targetCursor->element );
targetCursor = targetCursor->prev();
}
return result;
}
// 完整版 带符号运算的加法 （不是重载!!!）
BigInt& operator+( BigInt& bigInt ){
BigInt result = new BigInt; // 结果
result.isNegative = size() >= bigInt.size() ? isNegative : bigInt.isNegative; // 暂定为较大位数。 如果位数相同，根据最后一次计算结果修正。
int plus = 0; // 进位或借位
int res; // 单次计算结果
ChainNode<int>* cursor = last(); // 当前游标
ChainNode<int>* targetCursor = bigInt.last(); // 目标游标
while( cursor->prev() && targetCursor->prev() ){
res = isNegative ? -cursor->element : cursor->element
+ bigInt.isNegative ? -targetCursor->element : targetCursor->element
+ plus; // 我们把大数中的每一个数 都当成 a[i] * 10i来看。
// 绝对值超过>9的都需要向上进一位(一定是同符号)
// 不同符号 结果小于0的 需要借位
// 同符号小于0，不同符号大于0小于10的都可以忽略
// 小于0的时候 res需要取绝对值，保持元素的非负
if( res >9 || res<-9 ){
plus = 1;
}else if( res < 0 ){
plus = isNegative == bigInt.isNegative ? 0 : -1;
res = -res;
}
result.prepend(res);
}
if( size() == bigInt.size() ){ // 修复位数相同的问题
if( plus>0 ){
result.prepend(1); // 一定是同符号的，直接+1
}else if( plus<0 ){
result.isNegative = true; // 此时已经无法借位了，确认最终结果为负数
}
}
// 任意链表仍有元素未计算，继续补齐
while( cursor->prev() ){
result->prepend( cursor->element + plus );
plus = 0;
cursor = cursor->prev();
}
while( targetCursor->prev() ){
result->prepend( targetCursor->element + plus );
plus = 0;
targetCursor = targetCursor->prev();
}
// 修复首位为0的情况 // 全部删除则为空 即0
while( result.first().element == 0 ){
result.remove( result.first() );
}
return result;
}
// 在有符号加法的前提下，减法运算就简单多了
BigInt& operator-( BigInt& bigInt ){
bigInt.isNegative = !bigInt.isNegative; // 符号位颠倒
BigInt result = *this + bigInt;
bigInt.isNegative = !bigInt.isNegative; // 恢复
return result;
}
}
复杂度O(n)
template <class T>
void chain<T>::theSize( int n ){
chainNode<T> current = firstNode();
int i=0, max = _size < n ? _size : n;
// 由于不是双向链表，所以需要先到达n的极点
while( i < max ){
current = current->next();
i++;
}
chainNode<T> tmp;
// 如果有多余的
while( _size > n ){
tmp = current->next();
delete current; // 系统会执行element析构
current = tmp;
}
_size = n;
}复杂度O(n) 在实际使用的时候，链表一般不用index表示法来获取或设置元素。因为每次都相当于O(n)的复杂度。
template <class T>
void chain<T>::checkIndex( int theIndex ){
if( theIndex <0 || theIndex >= _size ){
throw illegalIndex("Out of range");
}
}
template <class T>
void chain<T>::set( int theIndex, T& theElement ){
checkIndex(theIndex);
chainNode<T>* current = firstNode();
int i = 0;
while( i < _size ){
current = current->next();
}
current->element.~T(); // 析构
current->element = theElement;
}复杂度O(n) 和上面的setSize类似，做一次遍历，之后将切割掉的部分接起来即可。
template <class T>
void chain<T>::setSize( int fromIndex, int toIndex ){
checkIndex(fromIndex);
checkIndex(toIndex);
chainNode<T>* current = firstNode();
int i=0;
// fromIndex的极点
while( i < fromIndex ){
current = current->next();
i++;
}
chainNode<T>* tmp;
while( i < toIndex ){
tmp = current->next();
delete current; // 系统会执行element析构
current = tmp;
}
_size -= toIndex-fromIndex +1; // 考虑左右闭区间
}复杂度O(n) 遍历元素并比对，不即时返回。
template <class T>
int chain<T>::lastIndex( T& theElement ) const{
if( empty() ) return -1;
chainNode<T>* current = firstNode();
int i = 0, lastIndex = -1;
while( i< _size ){
if( current->element == theElement ){
lastIndex = i;
}
current = current->next();
i++;
}
return lastIndex;
}
复杂度O(n) 实际上重载应该包含两种，分别是提供左值，右值返回。
template <class T>
const T& chain<T>::operator[](int n) const{ } // 右值
T& chain<T>::operator[]( int n) const{ // 左值
int i = 0;
chainNode<T>* current = firstNode();
while( i < n ){
current = current->next();
}
return current->element;
}复杂度O(n) 同步遍历两个链表元素，一旦发现不同元素返回false。
template <class T>
bool chain<T>::operator==( chain<T>& c) const{
if( size() != c.size() ) return false;
chainNode<T>* current = firstNode();
chainNode<T>* target = c.firstNode();
int i = 0;
while( i < size() ){
if( current->element !== target->element ) return false;
current = current->next();
target = target->next();
}
return true;
}复杂度O(n)
template <class T>
bool chain<T>::operator!=( chain<T>& c) const{
return !*this == c;
}复杂度O(n) 略微需要注意的是，除了最后一项的值完全相等以外，其他的相等 都不能判断非<。 所以在遍历的靠前阶段，== 都应该算成功，只有最后一项相等判断非小于。
template <class T>
bool chain<T>::operator<( chain<T>& c) const{
if( size() > c.size() ) return false;
chainNode<T>* current = firstNode();
chainNode<T>* target = c.firstNode();
int i = 0;
while( i < size() ){
if( current->element > target->element ){
return false;
}else{
current = current->next();
target = target->next();
}
}
if( current->element == target->element ) return false;
return true;
}1### 2. L = (a,b,c,d,e) ... 做图
初始状态:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| a | b | c | d | e |
insert(0,f)
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| f | a | b | c | d | e |
insert(3,g)
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| f | a | b | g | c | d | e |
insert(7,h)
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| f | a | b | g | c | d | e | h |
earse(0)
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| a | b | g | c | d | e | h |
erase(4)
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| a | b | g | c | e | h |
二维数组的话要基于Array设计一个矩阵类，其中的每一行都是一个Array对象。
template <class T>
class ArrayMatrix: public Array{
void changeLength2D( int x, int len );
}
template <class T>
void ArrayMatrix::changeLength2D( int rowIndex, int len ){
checkIndex(x);
get(rowIndex).changeLength(len);
}好像题目描述有问题。 我自己写的是提供一个是否自动扩容的参数。如果配置为不自动扩容则在超出的时候抛出异常。
enum class ARRAY_AUTO_CAPACITY
{
DISABLED = 0,ENABLED = 1
};
template <class T>
class Array{
public:
Array(int initCapacity = ARRAY_DEFAULT_CAPACITY, ARRAY_AUTO_CAPACITY autoCapacity = ARRAY_AUTO_CAPACITY::DISABLED);
void checkMax();
private:
ARRAY_AUTO_CAPACITY _autoCapacity = ARRAY_AUTO_CAPACITY::DISABLED;
}
template<class T>
inline void Array<T>::checkMax()
{
if (_size >= _capacity) {
switch (_autoCapcity)
{
case ARRAY_AUTO_CAPACITY::ENABLED:
changeCapacityTo(_capacity << 1);
break;
case ARRAY_AUTO_CAPACITY::DISABLED:
throw illegalInputData("Array is full.");
break;
default:
break;
}
}
}实际上就是改变数组长度， 长度为size或1。 这里我基于我改写的 changeCapacityTo()来实现，实际上是一回事。
复杂度是O(n)
void trimToSize(){
changeCapacityTo( _size>0 ? _size : 1 );
}
template<class T>
inline void Array<T>::changeCapacityTo(int newCapacity)
{
T* newElements = new T[newCapacity];
_capacity = newCapacity;
_size = newCapacity < _size ? newCapacity : _size;
for (int i = 0; i < _size; i++)
{
newElements[i] = _elements[i];
}
delete[] _elements;
_elements = newElements;
}这一题，同样题目描述是有问题的。 见上一题changeCapacityTo()
T& operator[]( int n){
checkIndex(n);
return _elements[n];
}template<class T>
bool operator==( const Array<T>& targetArray ) const{
if( size()!= targetArray.size() ){
return false;
}
for( int i=0; i<size();i++ ){
if( get(i) != target.get(i) ){
return false;
}
}
return true;
}
template<class T>
bool operator!=( const Array<T>& targetArray ){
return !*this == targetArray;
}见8 . 其中!= 替换为>
字符串匹配是搜索算法的基础，也是数据结构中一个十分有用的算法分支，我在学习KMP和BMBC算法的时候就觉得听的云里雾里，但经过一些实操和分析不难发现，这几个算法都是很好理解，并且对算法有很务实启发的。
以下我从零开始梳理以下如何建立一个清晰，并且有一定模式的理解这两个算法的思路。
从一个字符串中查询是否完全包含另一个字符串的过程。如果有则返回起始位置，无则匹配失败。 例： 在 "这是一个多美丽又遗憾的世界" 匹配 "美丽" 应该返回5. 匹配"太美丽" 失败。
前菜开始：
令 字符串
S = "这是一个多美丽又遗憾的世界"
模式串(待匹配子串)
s = "美丽"
循环遍历S并且在每一次S[i]与 s[j=0]匹配时，依次比较 S[i++] 与 s[j++]，
若成功则可以返回当前的 i-j 即为第一个字符所在的位置，失败则 i = i-j，再右移1位继续比较。
* 边界情况，当 i> m-n 时，宣告失败。 也就是说剩余可以配的元素已经不足够了，无需比较即告失败。
另外，约定查找失败时，返回-1；
算法示例:
int matchStr( char * S, char * s )
{
size_t m = strlen(S), n = strlen(s);
int i =0, j = 0;
while( i < m-n+1 && j<n ){
if( S[i] == s[j] ){
i++;j++;
}else{
i -= j-1; // i = i-j+1
j = 0;
}
}
return j==n ? i-j : -1;
// 当且仅当j与n相等时，模式串最后一位匹配成功
}接下来才是正餐：
优化的可能性仔细分析一下，就是如何减少没必要的匹配。 首先我们看一下，模式串都有哪些可能性呢？ （这里只需要考虑前缀，因为如果不是前缀重复，发生失配的时候一定是要从第一位开始比较的）
1 . 真前缀永不重复
a b c d e f g
2 . 单元素真前缀重复 / 真·一元前缀字串 重复
a a a a b c a a e
3 . 真·多元前缀字串重复
a b c a b c a b c a a b
那么接下来，分别看一下这几种不同的模式串，分别有怎样的优化方式。
在C++中创建数组的时候需要声明数组的长度，在声明一个二维数组的参数时，则至少需要确认第二维的长度，否则就无法完成编译。 为什么呢，我们可以用一张图来表示c++二维数组在内存中的表示就理解了。
实际上在创建数组的时候，c++是根据最低维，也就是最靠后的那个维度最大值来分配连续内存空间的。譬如int[2][5]就会分配10*4个字节空间出来，如果不知道最后一个维度，c++就不知道如何开辟内存空间了。
二维数组返回的就是整个数组的首元素地址。 而访问则是根据最后维的长度进行运算后得出：
/*
* c++ 二维数组
*
* hello@shezw.com 2020.07.03
*/
#include <iostream>
#include <string>
using namespace std;
int main()
{
int a[2][5] = {1,2,3,4,5,6,7,8,9,10};
for( auto e:a ){
printf( "%p : %d \n",e,*e );
}
printf( "%p : %d \n",&a[1][3],a[1][3] );
printf( "%p : %d \n",&a[0][8],a[0][8] );
}输出:
0x7fffa508a870 : 1
0x7fffa508a884 : 6
0x7fffa508a890 : 9
0x7fffa508a890 : 9 可以看到 a[0][8] 其实是完全等价于 a[1][3] 的,实际上a[1][3] 就是从第一个空间开始往后数第3+1*5 = 8个。
为了调用和使用方便，我这里设计一个Matrix模板类，专门用于这样的动态二维数组的使用。
/*
* c++ 二维数组
*
* hello@shezw.com 2020.07.03
*/
#include <iostream>
#include <string>
using namespace std;
template <typename T>
class Matrix{
private:
T ** _elements;
int _colSize;
int _rowSize;
public:
Matrix( int rows, int cols ){
_colSize = cols;
_rowSize = rows;
_elements = new T * [rows];
for( int i=0;i<rows;i++ ){
_elements[i] = new T [cols]();
}
}
~Matrix(){
for( int i=0;i<_rowSize;i++ ){
delete [] _elements[i];
}
delete [] _elements;
}
int getSize(){ return _colSize * _rowSize; };
int colSize(){ return _colSize; };
int rowSize(){ return _rowSize; };
// 函数形式
const T & get( int row, int col ){
return _elements[row][col];
}
// 重载操作符形式
T* & operator[]( int row ){
return _elements[row];
}
// 重载操作符形式 只读
const T* & operator[]( int row) const{
return _elements[row];
}
void print(){
for( int i=0; i< _rowSize; i++ ){
printf( "\n row %p: \n", _elements[i] );
for( int j=0; j< _colSize; j++ ){
printf( " col %p - %d\n", &_elements[i][j], _elements[i][j] );
}
}
}
};
int main()
{
Matrix<int> m(3,5);
m[2][1] = 15;
m.print();
}
/*
* 祖玛 Zuma
*
* hello@shezw.com 2020.06.29
*/
#include <iostream>
#include <string>
#include <queue>
using namespace std;
struct opr{
int t;
char c;
opr( int target, char color ){
t = target;
c = color;
}
};
void checkElimination( string & balls, int cursor ){
if( balls.empty() ){ return; }
int i = 1; int l = cursor, r = cursor, len = balls.size();
while( cursor-i > -1 ){
if( balls[cursor-i] != balls[cursor] ) break;
l = cursor - (i++);
}
i = 1;
while( cursor+i < len ){
if( balls[cursor+i] != balls[cursor] ) break;
r = cursor + (i++);
}
if( r - l > 1 ){
balls.erase( l,r-l+1 );
if( balls.size()>2 ) checkElimination( balls, l ); // 删除[l,r]区间后 如果存在继续消除可能时，原右侧必不为空，右侧第一个将取代原L。
}
}
int main()
{
string balls; int count; // 主要变量
int t; char c; // 缓存变量
cin>>balls; // 读取初始化彩球
cin>>count; // 读取初始化数量
queue<opr> oprs; // 操作队列
while( cin >> t ){ // 读取数字
cin >> c; // 读取颜色
oprs.push( opr(t,c) ); // 压入队列
}
while( !oprs.empty() ){
// cout<< oprs.front().t << " " << oprs.front().c << endl;
t = oprs.front().t;
c = oprs.front().c;
balls.insert( t, 1, c );
checkElimination( balls, t );
oprs.pop();
cout << (balls.empty() ? "-" : balls) << endl;
}
// cout << oprs.size() << endl;
// cout<< balls << endl << count << endl << oprs.front().c << endl;
}
由于清华judge是不允许使用SLT的，所以使用自建QUEUE来完成。
/*
* 祖玛 Zuma
*
* hello@shezw.com 2020.06.29
*/
#include <iostream>
#include <string>
using namespace std;
struct opr{
int t;
char c;
opr(){}
opr( int target, char color ){
t = target;
c = color;
}
};
template <typename T>
struct qe{
qe<T>* prev;
qe<T>* next;
T data;
qe(){}
qe( T d, qe<T>* p = NULL, qe<T>* n = NULL ){
data = d; prev = p; next = n;
}
};
template <typename T>
class queue{ // 专为本算法特别定制队列,简化版
private:
int _size = 0;
public:
qe<T>* _head;
qe<T>* _tail;
queue(){
_size = 0;
_head = new qe<T>;
_tail = new qe<T>;
_head->next = _tail; _head->prev = NULL;
_tail->prev = _head; _tail->next = NULL;
}
~queue(){
}
int size(){return _size;}
void push( T data ){
qe<T>* newQe = new qe<T>( data, _tail->prev, _tail );
_tail->prev->next = newQe;
_tail->prev = newQe;
_size++;
}
void pop(){
if( empty() ) return;
_head->next = _head->next->next;
delete _head->next->prev;
_head->next->prev = _head;
_size--;
}
bool empty(){
return _size == 0;
}
const T & front(){
return _head->next->data;
}
};
void checkElimination( string & balls, int cursor ){
if( balls.empty() ){ return; }
int i = 1; int l = cursor, r = cursor, len = balls.size();
while( cursor-i > -1 ){
if( balls[cursor-i] != balls[cursor] ) break;
l = cursor - (i++);
}
i = 1;
while( cursor+i < len ){
if( balls[cursor+i] != balls[cursor] ) break;
r = cursor + (i++);
}
if( r - l > 1 ){
balls.erase( l,r-l+1 );
if( balls.size()>2 ) checkElimination( balls, l ); // 删除[l,r]区间后 如果存在继续消除可能时，原右侧必不为空，右侧第一个将取代原L。
}
}
int main()
{
string balls; int count; // 主要变量
int t; char c; // 缓存变量
cin>>balls; // 读取初始化彩球
cin>>count; // 读取初始化数量
queue<opr> oprs; // 操作队列
while( cin >> t ){ // 读取数字
cin >> c; // 读取颜色
oprs.push( opr(t,c) ); // 压入队列
}
while( !oprs.empty() ){
// cout<< oprs.front().t << " " << oprs.front().c << endl;
t = oprs.front().t;
c = oprs.front().c;
balls.insert( t, 1, c );
checkElimination( balls, t );
oprs.pop();
cout << (balls.empty() ? "-" : balls) << endl;
}
// cout << oprs.size() << endl;
// cout<< balls << endl << count << endl << oprs.front().c << endl;
}
编译结果 95/100 最坏结果 204ms 14388KB。
这样看来还需要进一步优化。 20200629
数据结构、算法与应用 第一张练习 26
两个代码之间的 海明距离 (Hamming distance) 是对应位不等的数量。 例如：100和010的海明距离是2。 一个（二进制）格雷码是一个代码序列，其中任意相邻的两个代码之间的海明距离是1。 子集生成的序列 000，100，010，001...111 不是格雷码，因为100，010海明距离是2。 而三位代码序列 000，100，110，010，011，111，101，001是格雷码。
在代码序列的一些应用中，从一个代码到下一个代码的代价取决于它们的海明距离。因此我们希望这个代码序列是格雷码。格雷码可以用代码变化的位置序列简洁地表示。 对于上面的格雷码，位置序列是1，2，1，3，1，2，1.
令g(n)是一个n元素的格雷码的位置变化序列。以下是g的递归定义：
1 n=1
g(n-1),n,g(n-1) n>1注意这个是位置变化序列，并不是格雷码生成。
以下为算法
#include <iostream>
#include <cmath>
/*
* 格雷码序列数量是 2^n，相应的变化序列数量是 2^n - 1
*/
int * GrayCodeChangeSequence( int n ){
int len = pow(2,n)-1;
int * arr = new int[len];
if( n<2 ){ arr[0]=1; return arr; }
int half = (len-1)>>1;
int * half_arr = GrayCodeChangeSequence( n-1 );
for( int i=0; i<half; i ++ ){
arr[i] = half_arr[i];
}
arr[half] = n;
for( int i=0; i<half; i ++ ){
arr[i+half+1] = half_arr[i];
}
return arr;
}
void testGCCS( int n ){
int * b = GrayCodeChangeSequence(n);
for( int i = 0; i< pow(2,n)-1 ; i++ ){
std::cout << b[i] << ' ';
}
std::cout << endl;
delete[] b;
}
int main()
{
testGCCS(1);
testGCCS(2);
testGCCS(3);
testGCCS(4);
testGCCS(5);
}
测试分别输出：
1
1 2 1
1 2 1 3 1 2 1
1 2 1 3 1 2 1 4 1 2 1 3 1 2 1
1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1实际上格雷码修改序列生成和斐波那契数列的生成效率是需要进一步优化的，原因在于每一次收到递归结果，都需要遍历一次结果并且覆盖到当前的序列中。从渐进意义上来说，复杂度是O(n2) 而且相对于序列的长度增长渐进意义上远大于n，这个时候如果能够在一次遍历的情况下配合少量计算那么可以将复杂度降低至O(n)
数据结构、算法与应用 第一张练习 23
当两个非负整数x和y都是0的时候，他们的最大公约数是0. 当两者至少有一个不是0的时候，他们的最大公约数是可以除尽二者的最大整数。 因此gcd(0,0)=0, gcd(10,0)=gcd(0,10)=10,而gcd(20,30)=10.
求最大公约数的欧几里得算法（Euclid's Algorithm）是一个递归算法：
x (y=0)
gcd(y,x mode y) (y>0)其中mod是模数运算子（modulo operator），相当于C++取余操作符%.
以下为算法
int GCD( int x, int y ){
if( y==0 ){
return x;
}
return GCD( y, x%y );
}
最近回复