2016年9月8日 星期四

河內塔 非遞迴解

河內塔 簡易的 非遞迴解

有別於普通利用數學找出規律的方式
僅僅只有3個流程1個口訣,即可解出來
  1. [組牌]
  2. [發牌]
  3. [收牌或換牌]
  • 不可重複上一步
有實驗過花幾分鐘記住口訣或看懂口訣,即便完全沒接觸的人
也能夠輕易解出多層的河內塔,當初實驗的人還蠻驚訝的XDD
代碼有些亂,有打算打掉重來全部套C++來寫
核心流程:
/**********************************************************
Name : KUAS-Hw/Hw08
DATE : 2016/04/06
Final: 2016/06/15
By   : CharlotteHong
**********************************************************/
//=========================================================
#include <iostream>
#include <stdio.h>
#include "fun\hanoi.h"
#include "fun\doulink.h"
using namespace std;
//=========================================================
int main(int argc, char const *argv[]){
    /* 開頭節點 */
    node** ht = new node*[3];
    ht[0] = node_creat(-1);
    ht[1] = node_creat(-1);
    ht[2] = node_creat(-1);
    /* 批次匯入節點 */
    int len = 8; //幾個盤子
    int *data = new int[len];
    for (int i = 0; i < len; ++i)
        data[i] = len-i;
    nodep_input(ht[0], data, len);
    //=====================================================
    // 計算最短步數
    int setup=2;
    for (int i = 0; i < len-1; ++i){
        setup*=2;
    }setup--;
    //=====================================================
    // 開始運行
    for (int i = 0; i < 1; ++i){
        cout << "-------------------[" << i << "]" << "" << endl;
        cout << "上一步: ";hanoi_logpri(ht);
        /* 1.組牌 */
        if (hanoi_handdif(ht)==1){
            if (hanoi_defrag(ht) == 0){
                cout << "  def" << endl;
                continue;
            }
        }
        /* 2.發牌 */
        if (hanoi_checksent(ht)==1){
            if (hanoi_sent(ht) == 0){
                cout << "  sen" << endl;
                continue;
            }
        }
        /* 3.收or換 */
        // 差 (雙)
        if (hanoi_handdif(ht) % 2 == 0){
            // 沒有重複上一步的話 => 小收回
            if (hanoi_receive(ht, 0) == 0){
                cout << "  sre" << endl;
                continue;
            }
            // 重複上一步的話 => 大收
            else{
                hanoi_receive(ht, 1);
                cout << "  bre" << endl;
                continue;
            }
        }
        // 差 (單)
        else{
            // 沒有重複上一步的話 => 小換
            if (hanoi_change(ht)==0){
                cout << "  chg" << endl;
                continue;
            }
            // 重複上一步的話 => 大收
            else{
                hanoi_receive(ht, 1);
                cout << "  bre" << endl;
                continue;
            }
        }
        cout << "Nothing" << endl;
    }
    cout << "-------------------[" << setup << "]" << "" << endl;
    cout << "上一步: ";hanoi_logpri(ht);
    //=====================================================
    /* 印出節點 */
    cout << "==============================================" <<endl;
    hanoi_pri(ht);
    //=====================================================
    /* 釋放記憶體 */
    for (int i = 2; i >= 0; --i){
        node_deleteall(ht[i]);
        delete [] ht[i];
    } delete [] ht;
    //=====================================================
    return 0;

}

C++ 如何開啟 RAW 圖檔 [OpenRAW 2.31]

C++ 如何開啟 RAW 圖檔 [OpenRAW 2.31]

解決的問題:
  • 用什麼型態儲存更適合
  • 控制開檔、讀檔、存檔與匯出檔案
  • 繪製簡易的數值統計直方圖
  • 使用 [] 下標存取 class 宣告的物件
  • 方法 引入參數簡化
  • 更有效率的取得遮罩

OpenRAW 2.31 refrence

如何引入使用
標頭僅需引入 #include "OpenRAW"
使用時須使用命名空間 namespace imr
可在標頭引入 using namespace imr;
typedef unsigned char imch;
typedef size_t imint;

namespace imr{
    class ImrSize{
    public:
        ImrSize(imint y, imint x);
        imint width;
        imint high;
    };

    class ImrCoor{
    public:
        ImrCoor(int y, int x);
        int y;
        int x;
    };

    class ImrMask{
    public:
        ImrMask(ImrSize masksize);
    private:
        vector<imch> mask;
    };

    class imgraw {
    public:
        imgraw(ImrSize size);
    private:
        vector<imch> img_data;
    };
};

各項類別屬性與建構說明


ImrSize 畫布大小

ImrSize 用來描述畫布畫布大小
大小可在建構時設置
如,設置一個256x256大小的畫布
ImrSize size(256,256);
使用時可使用公開變數
size.widthsize.high
型態為 size_t
某些情況可需要轉態
for (int i=0; i<=(int)size.high, ++i)

ImrCoor 座標位置

ImrCoor 用來描述座標位置
座標可在建構時設置
如,設置一個(0,0)的座標
ImrCoor coor(0,0);
使用時可使用公開變數
size.ysize.x
型態為 int

重載

ImrCoor 提供基本的加減乘除運算子
ImrCoor a(1,2), b(3,4), c;
c = a+b;
C則為(4,6)依此類推

ImrMask 遮罩陣列

ImrMask 用來儲存遮罩陣列
使用時需再主程式宣告,並接住(複製)
方法產生的類別,即可使用。
ImrMask mask = img.getMask();
由於僅是接住方法產生的陣列
故不需建構任何資訊(由方法建構)
方法用法請參考該類別說明欄位
使用時可直接使用[下標]存取指標陣列
cout << mask[0] << endl;
mask[0] = 1;
型態為unsigned char*
雖然為動態陣列,不過會智能解構
不必擔心主程式接住後記憶體釋放問題
因為是動態陣列,主程式用複製的方式
只複製指標並不會拖垮效能
不過讀取的時候那仍然是複製數值
盡可能使用 maskVal() 取代

方法

imch & at2d(size_t y, size_t x);

以二維的方式存取位置(y,x)的遮罩
cout << mask.at2d(0,0);
mask.at2d(0,0) = 0;

void sort(size_t len, size_t start);

插入排序遮罩大小,由小到大
mask.sort(); 排序全部
其中可以自由指定那些需要排序
sort(len, start);
比如說一共有4個我要排序中間兩個
長度是2,從mask[1]開始排序
mask.sort(2,1);

imgraw OpenRAW主要類別

imgraw 用來儲存RAW圖檔
在建構時需設置圖檔大小
建構參數是 imgraw(ImrSize) 類別
如,設置一個256x256大小的圖檔
ImrSize size(256,256);
imgraw img(size);
你也可以一起設置
imgraw img(ImrSize(256,256));
設置錯誤的圖檔大小,基於RAW檔特性
程式是無法辨別並自動修正的
可能會產生不可預知的錯誤
使用時可直接使用[下標]存取圖檔資訊
cout << img[0] << endl;
img[0] = 1;
型態為vector<unsigned char>
注意因為型態是 unsigned char
如果超出255將會從0開始計算
修正方式請在處理時轉為其他型態
img[0] = 127;
double temp;
temp = (double)img[0] + (double)255;

if (temp > 255){
    temp=255;
}

img[0] = (unsigned char)temp;

方法

typedef unsigned char imch;
typedef size_t imint;

void read(string filename);

將檔案與主程式放到同一個位置
img.read("File name");
即可將圖檔讀入

void write(string filename);

img.write("File name");
填入輸出的檔名,通常會在圖像處理完畢後輸出

imch & at2d(size_t y, size_t x);

以二維的方式存取圖檔資訊
cout << img.at2d(y, x) << endl;
img.at2d(y, x)=img.at2d(y, x)+10;

void resize_canvas(ImrSize size);

重新定義畫布大小
img.resize_canvas(ImrSize(high, width))

imint w();

獲得寬
img.w();

imint h();

獲得高
img.h();

void pri_htg(string title);

印出直方圖
img.pri_htg("title name");

void setMaskSize(ImrSize masksize);

設定遮罩大小,使用getMask()前須事先指定
img.setMaskSize(ImrSize(3,3));

imch maskVal(ImrCoor ori, ImrCoor mas, ImrCoor shi);

取得遮罩數據
遮罩會自動檢查邊界,如果遇到邊界無法取值,自動補上邊界數值

使用說明
ImrCoor ori();
對應原圖的點
ImrCoor mas();
遮罩二維位置
ImrCoor shi();
偏移位置(可省略預設 -1,-1)
假設
ori(1,1),
mas(2,2),
shi(-1,-1),
原圖(5x5)
○ ○ ○ ○ ○ 
○ ○ ○ ○ ○ 
○ ○ ○ ○ ○ 
○ ○ ○ ○ ○ 
○ ○ ○ ○ ○ 

遮罩參考點 ori(1,1)
○ ○ ○ ○ ○ 
○ ● ○ ○ ○ 
○ ○ ○ ○ ○ 
○ ○ ○ ○ ○ 
○ ○ ○ ○ ○ 

加上位移 shi(-1,-1)
● ○ ○ ○ ○ 
○ ○ ○ ○ ○ 
○ ○ ○ ○ ○ 
○ ○ ○ ○ ○ 
○ ○ ○ ○ ○ 

放大這個部分 
● ● ● ○ ○ 
● ● ● ○ ○ 
● ● ● ○ ○ 
○ ○ ○ ○ ○ 
○ ○ ○ ○ ○ 

取 mas(2,2)
● ● ● 
● ● ● 
● ● ○ 

img.maskVal(ImrCoor(1,1), ImrCoor(2,2));
可得 [ 若shi留空,預設是shi(-1,-1) ]
○ ○ ○ ○ ○ 
○ ○ ○ ○ ○ 
○ ○ ● ○ ○ 
○ ○ ○ ○ ○ 
○ ○ ○ ○ ○

ImrMask getMask(ImrCoor ori, ImrCoor shi);

取得遮罩陣列(一維)
需先設置遮罩大小 img,setMaskSize(ImrSize(3,3));
點會複製到動態陣列上,除非有要排序,否則會比較花費時間
// 設定遮罩
img.setMaskSize(ImrSize(4,4));
// 取得Mask陣列及排續 getMask(原點位置)
ImrMask mask = img.getMask(ImrCoor(2,2));

cout << endl<< "setMaskSize" << endl;
for (int j = 0, c = 0; j < 4; ++j){
    for (int i = 0; i < 4; ++i, c++){
        cout << (int)mask[c] << " ";
        // cout << mask.at2d(j,i);
    }cout << endl;
}
原圖(5x5)
○ ○ ○ ○ ○ 
○ ○ ○ ○ ○ 
○ ○ ○ ○ ○ 
○ ○ ○ ○ ○ 
○ ○ ○ ○ ○ 

對應原圖的點
○ ○ ○ ○ ○ 
○ ○ ○ ○ ○ 
○ ○ ● ○ ○ 
○ ○ ○ ○ ○ 
○ ○ ○ ○ ○ 

偏移位置 shi(-1,-1)
[ 若shi留空,預設是shi(-1,-1) ]
○ ○ ○ ○ ○ 
○ ● ○ ○ ○ 
○ ○ ○ ○ ○ 
○ ○ ○ ○ ○ 
○ ○ ○ ○ ○ 

獲得(4x4)
○ ○ ○ ○ ○ 
○ ● ● ● ● 
○ ● ● ● ●  
○ ● ● ● ●  
○ ● ● ● ●

2016年9月1日 星期四

動態陣列,注意事項與二維一次性宣告方法

動態陣列,注意事項與二維一次性宣告方法

tags:C++

delete 與 delete [] 差異

兩者都會呼叫解構函式,差別在於
後者只會呼叫開頭指標的解構函式
簡單來說今天你配置了arr[n]的動態陣列
如果你僅使用 delete 那只會解構 arr[0]
後面全部都不會被解到,可怕的是
這並不意味不能編譯與執行。
為了避免這種情況,記得養好習慣
聽起來很複雜,用一句話概括
方括配方括

這裡如果還不夠明白,簡單測試一下就能馬上了解了
#include <iostream>
class cls{
public:
    cls(){ std::cout << "constructor" << std::endl; }
    ~cls(){ std::cout << "destructor" << std::endl; }
};
int main(){
    cls* p = new cls[5];
    delete [] p;
    return 0;
}

釋放的指標最好手動指向空指標

上面我們可以知道 new[] 必須搭配 delete []
這裡還有一個小問題,你可以嘗試著把上方的代碼
印出釋放後的指標,你會發現指標沒有指向 0
這不是太大問題,但是如果造成問題了(肯定會有的
只是用到機率不大),應該不容易被找到問題點
養成習慣最好在釋放後手動指向空指標
空指標這裡簡單的敘述什麼該用什麼
  • C 使用 NULL
  • C++ 使用 0
  • c++11 使用 nullptr
千萬不要因為看起來不重要,且實際實際執行
時確實無法直接看出差別,就忽視了或偷懶

如果你不想 delete 那麼多

可以算出長度,一次宣告出全部
下標仍然可以使用,直接加上就好
void** new2d(int h, int w, int size){
    register int i;
    void **p;
    p = (void**)new char[h*sizeof(void*) + h*w*size];
    for(i = 0; i < h; i++)
        p[i] = ((char *)(p + h)) + i*w*size; 
    return p;
}
因此就可以用這 function 動態建立二維陣列
data = (int **)new2d(data_height, data_width, sizeof(int));

可以把他整合到Macro
在程式前頭增加
#define NEW2D(H, W, TYPE) (TYPE **)new2d(H, W, sizeof(TYPE))
便可簡化剛剛動態配置二維陣列寫法
data = NEW2D(data_height, data_width, int);

參考資料

  1. [問題] 指標 直接存取與使用下標存取 差異
    https://www.ptt.cc/bbs/C_and_CPP/M.1472632682.A.DE7.html
  2. 關於指標的new、delete、NULL的觀念問題
    http://www.programmer-club.com.tw/showSameTitleN/c/37427.html
  3. Re: [心得] 空指標常數(null pointer constant)
    https://www.ptt.cc/bbs/C_and_CPP/M.1461824349.A.B47.html