permutation

留下评论

Alexander Bogomolyn’s unordered permutation algorithm

#include <stdio.h>


void print(const int *v, const int size)
{
if (v != 0) {
for (int i = 0; i < size; i++) {
printf("%4d", v[i] );
}
printf("\n");
}
} // print


void visit(int *Value, int N, int k)
{
static level = -1;
level = level+1; Value[k] = level;

if (level == N)
print(Value, N);
else
for (int i = 0; i < N; i++)
if (Value[i] == 0)
visit(Value, N, i);

level = level-1; Value[k] = 0; //回溯时要恢复共享变量
}


main()
{
const int N = 4;
int Value[N];
for (int i = 0; i < N; i++) {
Value[i] = 0;
}
visit(Value, N, 0);
}

University of Exeter algorithm

#include <stdio.h>

void print(const int *v, const int size)
{
if (v != 0) {
for (int i = 0; i < size; i++) {
printf("%4d", v[i] );
}
printf("\n");
}
} // print


void permute(int *v, const int start, const int n)
{
if (start == n-1) {
print(v, n);
}
else {
for (int i = start; i < n; i++) {
int tmp = v[i];

v[i] = v[start];
v[start] = tmp;
permute(v, start+1, n);
v[start] = v[i];
v[i] = tmp;
}
}
}


main()
{
int v[] = {1, 2, 3, 4};
permute(v, 0, sizeof(v)/sizeof(int));
}

An Ordered Lexicographic Permutation Algorithm based on
one published in Practical Algorithms in C++

#include <stdio.h>

void print(const int *v, const int size)
{
if (v != 0) {
for (int i = 0; i < size; i++) {
printf("%4d", v[i] );
}
printf("\n");
}
} // print


void swap(int *v, const int i, const int j)
{
int t;
t = v[i];
v[i] = v[j];
v[j] = t;
}


void rotateLeft(int *v, const int start, const int n)
{
int tmp = v[start];
for (int i = start; i < n-1; i++) {
v[i] = v[i+1];
}
v[n-1] = tmp;
} // rotateLeft


void permute(int *v, const int start, const int n)
{
print(v, n);
if (start < n) {
int i, j;
for (i = n-2; i >= start; i--) {
for (j = i + 1; j < n; j++) {
swap(v, i, j);
permute(v, i+1, n);
} // for j
rotateLeft(v, i, n);
} // for i
}
} // permute



Advertisements

C++之封装探究

留下评论

C++定义的组件会存在版本问题,源至C++的编译模型,它不能支持独立二进制组件的设计。C++的编译模型要求
客户必须知道对象的布局结构,从而导致了客户和对象可执行代码之间的二进制耦合关系。这种耦合性使得
在不重新编译客户的情况下,类的实现很难被替换,就算程序采用动态链接方式。
虽然程序编译/链接存在不兼容性,但是我们仍然可以做一些基本假设,确定语言实现中具有同一形式的地方:
1. 复合类型(比如C风格的struct)在运行时的表现形式对于不同的编译器往往会保持不变;
2. 所有的编译器都强制使用同样的顺序传递函数参数,并且堆栈的清理必须按照统一的方式进行。例如Win32
   API中使用WINAPI/WINBASEAPI宏就是这一要求的一种解决方案。
3. 最重要的假设:某个给定平台上的所有C++编译器都实现了同样的虚寒树调用机制。
vtbl的布局结构有两种基本技术实现方式:一种是CFRONT(Solaris编译器); 一种是adjustor thunk(Win32编译器)。
具体参见"Inside the C++ Object Model"。
class FastString : public IFastString {
    const int m_cch;
    char *m_psz;
public:
    FastString(const char *psz);
    ~FastString(void);
    int Length(void) const;
    int Find(const char *psz) const;
};
class IFastString {
public:
    virtual int Length(void) const = 0;
    virtual int Find(const char *psz) const = 0;
};
extern "C"
IFastString *CreateFastString(const char *psz);
******************************Test Code*****************************************
int f(void)
{
    IFastString *psf = CreateFastString("Hello World");
    int n = psf->Find("war");
    delete pfs; // Memory Leak!!!!!!!!!!!
    return n;
}
产生内存泄露的原因是因为析构函数不是虚函数,所以delete操作符并不能动态找到最终的
派生类的析构函数从而正确地销毁对象。
解决方案:注意,我们不能简单地把接口类的析构函数定义成虚函数,因为虚析构函数在vtbl
中的位置依赖于编译器的具体实现。一种可行的方法是在接口类中添加一个纯虚方法Delete,
以便让类自己实现销毁方式,但是这也需要客户程序在销毁对象前显示调用Delete方法。
******************************Test Code*****************************************
int f(void)
{
    IFastString *psf = CreateFastString("Hello World");
    if (psf)
    {
        int n = psf->Find("war");
        bfs->Delete();
    }
    return n;
}
 
这种实现方式仍然没有做到足够好的封装,因为这会泄露对象的一个实现细节:对象是被分配在
堆上的。因此,我们可以让对象自己管理其生命周期。
一种简单的解决方案就是采用引用计数。
class IExtensibleObject {
public:
    virtual void *Dynamic_Cast(const char *pszType) = 0;
    virtual void DuplicatePointer(void) = 0;
    virtual void DestroyPointer(void) = 0;
};
class IPersistentObject : public IExtensibleObject {
public:
    vitrual bool Load(const char *pszFileName) = 0;
    virtual bool Save(const char *pSzFileName) = 0;
};
class IFastString : public IExtensibleObject {
public:
    virtual int Length(void) = 0;
    virtual int Find(const char *psz) = 0;
};
class FastString : public IFastString,
                   public IPersitentObject {
private:
    int m_cch;
    char *m_psz;
    int m_cPtrs;
public:
    FastString(const char *psz);
    ~FastString(void);
    void *Dynamic_Cast(const char *pszType);
    void DuplicatePointer(void);
    void DestroyPointer(void);
  
    int Length(void) const;
    int Find(const char *psz) const;
    bool Load(const char *pszFileName);
    bool Save(const char *pszFileName);
};
Tips:IExtensibleObject并不是被虚继承的,因为虚继承也是依赖于编译器实现方式的; dynamic_cast也是如此。
      接口是一类某一范围内功能的集合,要以此对接口进行必要的拆分。
******************************Test Code*****************************************
void f(void)
{
    IFastString *pfs = NULL;
    IPersistentObject *ppo = NULL;
    psf = CreateFastString("Hello World");
    if (psf)
    {
         ppo = (IPersistentObject*)pfs->Dynamic_Cast("IPersistentObject");
         if (ppo)
         {
             ppo->Save("c:\\test.bat");
             ppo->DestroyPointer();
         }
         pfs->DestroyPointer();
    }
}

数据元素调整

留下评论

#include <iostream>
#include <string.h>

using namespace std;
typedef struct Record
{
    int key;
    int value;
} Record;

void Order(Record a[], int lenA)
{
    Record *endOfLink = NULL;
    for (int i = 0; i < lenA; ++i)
    {
        int tempI = i;
        endOfLink = &(a[a[tempI].key]);
        while(endOfLink != &a[tempI])
        {
            if (endOfLink->key !=tempI)
            {
                endOfLink = &(a[endOfLink->key]);
            }
            else
            {
                int next = a[tempI].key;

                Record temp;
                temp = a[tempI];
                a[tempI] = *endOfLink;
                endOfLink->key = temp.key;
                endOfLink->value = temp.value;

                tempI = next;
            }
        }
    }
}

int main()
{
    Record recs[10];
    for (int i = 0; i < 10; ++i)
    {
        recs[i].key = (i *123 + 1) % 10;
        recs[i].value = i *123 + 1;
    }
    for (int i = 0; i < 10; ++i)
    {
        cout <<recs[i].key << "." << recs[i].value << "   ";
    }
    cout << endl;
    Order(recs, 10);
    for (int i = 0; i < 10; ++i)
    {
        cout <<recs[i].key << "." << recs[i].value << "   ";
    }
    cout << endl;
    return 0;
}

无符号任意位正整数加法

留下评论

#include <iostream>
#include <string.h>

using namespace std;

typedef unsigned char BYTE;

int main()
{

    string s1;
    cout << "Please input the first number: " << endl;
    cin >> s1;
    int count1 = s1.length();
    BYTE a1[count1];
    memset(a1, 0, sizeof(a1));
    // Assuming both of the operands are unsigned.
    // And the length of the operand should be a little rational, tool, better less than 4K.
    for (int i = 0; i < count1; ++i)
    {
        if (s1[i] > ‘9’ || s1[i] < ‘0’)
        {
            cout << "illegal operand!!!" << endl;
            return 1;
        }
        a1[i] = s1[i] – ‘0’;
    }
    s1.clear();

    cout << "Please input the second number: " << endl;
    cin >> s1;
    int count2 = s1.length();
    BYTE a2[count2];
    memset(a2, 0, sizeof(a2));
    // Assuming both of the operands are unsigned.
    // And the length of the operand should be a little rational, tool, better less than 4K.
    for (int i = 0; i < count2; ++i)
    {
        if (s1[i] > ‘9’ || s1[i] < ‘0’)
        {
            cout << "illegal operand!!!" << endl;
            return 1;
        }
        a2[i] = s1[i] – ‘0’;
    }

    int carry = 0;
    BYTE *pa1 = a1;
    BYTE *pa2 = a2;
    int pp = count1;
    if (count1 < count2)
    {
        pp = count2;
        int temp = count2;
        count2 = count1;
        count1 = temp;
        pa1 = a2;
        pa2 = a1;
    }

    for (count2 -= 1, count1 -= 1; count2 >= 0; –count2, –count1)
    {
        pa1[count1] = pa1[count1] + pa2[count2] + carry;
        if (pa1[count1] >= 10)
        {
            carry = 1;
            pa1[count1] -= 10;
        }
        else
        {
            carry = 0;
        }
    }
    cout << "The output is: " << endl;
    if (carry != 0)
    {
        if (count1 >= 0)
        {
            pa1[count1] += carry;
        }
        else
        {
            cout << carry;
        }
    }
    for (int i = 0; i < pp; ++i)
    {
        cout << (int)(pa1[i]);
    }
    cout << endl;
    return 0;
}