code10111: Algorithm

顯示具有 Algorithm 標籤的文章。顯示所有文章

2012年3月13日星期二

C&C++: [問題] 新手發問"!!"的意思

！！
節錄部份

作者 Barros (Leila)                                       站內 Programming
標題 [問題] 新手發問　"!!"的意思
時間 Thu Mar 8 21:11:04 2012
───────────────────────────────────────

看資料結構的書的時候，應該是用c寫的吧
發現code裡出現 !! 這個符號
煩請解惑感激不盡~

節錄部份code:

BinQueue
Merge(BinQueue H1, BinQueue H2)
{
Bintree T1, T2, Carry=Null;
int i j;

if(H1->CurrentSize +H2->CurrentSize >Capacity)
    error("Merge would exceed capacity");
H1->CurrentSize += H2->CurrentSize;
for(i=0, j=1; j<= H2->CurrentSize; i++, j*=2)
}
     T1=H1->TheTrees[i];T2=H2->TheTrees[i];

switch( !!T1 + 2 * !! T2 + 4 * !! Carry)
{
      case 0: /*no trees*/
      case 1: /*only H1*/
           break;

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 219.84.2.1
→ Barros:因為google過了也找不到只好來這裡發問了       219.84.2.1 03/08 21:12
→ tropical72:是長得像這樣嗎？int a=5; if(!!a)..    123.195.165.40 03/08 21:13
→ tropical72:簡單的說,a是非0的話,!!a會傳回1；否則 123.195.165.40 03/08 21:14
→ tropical72:傳回0。                               123.195.165.40 03/08 21:14
※ 編輯: Barros          來自: 219.84.2.1           (03/08 21:29)
→ s66449:加了兩個not 不就等同互相抵消了??          114.27.187.150 03/08 22:13
→ s66449:有加和沒加是一樣的?                       114.27.187.150 03/08 22:13
→ tropical72:不同唷,a=1,b=5而言 :                  123.195.165.40 03/08 22:19
→ tropical72:a+=b; --> a+=5 ---> a=6;              123.195.165.40 03/08 22:20
→ tropical72:a+=!!b ---> a+=!(!5)-->a+=!0-->a+=1   123.195.165.40 03/08 22:20
→ tropical72:--> a=2;                              123.195.165.40 03/08 22:20
→ tropical72:(T1!=0)|((T2!=0)<<1)|((C!=0)<<2)      123.195.165.40 03/08 22:26
→ Barros:了解了，謝謝                                219.84.58.43 03/08 22:47
→ MOONRAKER:真是神祕。                               61.231.8.206 03/09 08:46
推 yauhh:一個!將整數變成布爾值,但邏輯意思是反的,     180.206.52.95 03/09 18:42
→ yauhh:再加!就回來了.                              180.206.52.95 03/09 18:43
→ yauhh:他做二件事,一是將整數對應為0,1,二是將0,1   218.160.108.73 03/09 21:56
→ yauhh:(true,false)反過來當作數字來用. 但例子中   218.160.108.73 03/09 21:57
→ yauhh:看起來作法好怪,邏輯運算當數字運算用,數字   218.160.108.73 03/09 21:57
→ yauhh:運算卻當位元運算用.                        218.160.108.73 03/09 21:58

作者 LPH66 (-858993460)                                   看板 Programming
───────────────────────────────────────

這是懶人用switch...

!! 是做兩次 boolean not

所以非零的會變成 1 是零的就還是 0

於是 !!T1 + 2 * !! T2 + 4 * !! Carry 這個算式

將三件事 (T1 != 0, T2 != 0, Carry != 0) 編碼成一個整數

若三者都為 0 則它會算出二進位的 000 = 十進位 0

若只有 T1 非 0 則它會算出二進位的 001 = 十進位 1

若只有 T2 非 0                    010 = 十進位 2

若只有 Carry 非 0                 100 = 十進位 4

等等

這樣就能以 switch 一次判斷三個條件的真假

你可以注意到這個 switch 裡的 case 有註解寫說這是什麼情況

就是這麼來的

※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.28.91

→ popcorny:我是覺得最起碼要用Macro包一下           114.32.239.120 03/11 14:20
→ popcorny:#define ISTRUE(x) (!!(x))               114.32.239.120 03/11 14:21
→ popcorny:可讀性跟你說的其實沒有那麼衝突          114.32.239.120 03/11 14:22

作者 adrianshum (Alien)                                   看板 Programming
───────────────────────────────────────

不是覺得這種精簡寫法一定有錯，但同樣做法，真的要寫得那麼
非直覺嗎？為什麼不可以寫成：
int t = 0;
if (T1) t |= 1;
if (T2) t |= 2;       // 或寫成 t |= (1<<1);
if (Carry) t |= 4;    // t |= (1 << 2)

switch (t) {
//..
}

再不然，寫成
int t = (T1? 1 : 0) | (T2 ? 2 : 0) | (Carry ? 4 : 0);
(以上 bitwise OR 可改用 +，看你自己喜好）

這樣單從 code 表面上就看得出是根據 T1, T2, Carry 來 turn-on
各個 bit。除非真的程式慢得連這一點點 performance 都要壓搾，
不然至少對我來說，上面的寫法比 !!T1 + 2 * !! T2 + 4 * !! Carry
看起來合理得多了

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 223.19.47.36

2011年11月6日星期日

慘遭助教修理的一道程式習題冼鏡光

慘遭助教修理的一道程式習題冼鏡光
http://blog.dcview.com/article.php?a=ADgAZgJlVGQ%3D

2011年11月2日星期三

菱形

原理:
n=3

　　＊　
　＊　＊　
＊　＊　＊　
　＊　＊　
　　＊　

令＊ =Ｘ

j
0 1 2
2　　Ｘ
1　ＸＸ
i 0ＸＸＸ
-1　ＸＸ
-2　　Ｘ

#include
int main(void)
{
int n, i, j;
scanf( "%d", &n);
for( i = n-1; i >= -n+1; --i )
{
for( j = 0; j <= n-1; ++j )
{
if( i <= j && -i <= j )
printf("* ");
else
printf(" ");
}
printf("\n");
}
return 0;
}

2011年10月23日星期日

Recursive

http://www.programmer-club.com/pc2020v5/Forum/ShowSameTitleN.asp?URL=N&board_pc2020=general&id=2830
作者 : chiuinan2(青衫)

(1) recursive algorithm：

Procedure HANOI(A,B,C,n) // 將n個環從A移到B //
if n<=0 then
print("error")
else if n=1 then
print(A,"→",B)
else
[ call HANOI(A,C,B,n-1);
print(A,"→",B);
call HANOI(C,B,A,n-1) ]
end

設計的主要觀念為：
1.將A柱中前n-1個環搬到C柱中暫置。（呼叫自己）
2.將A柱中剩下最大的環搬到B柱中。
3.將C柱中的n-1個環搬到B柱中。（呼叫自己）

(2)將recursive改成non-recursive的做法有很多種。如果已經知道recursive algorithm的話，最正統的方法便是直接將它化成non-recursive的形式。由recursive algorithm化成non-recursive algorithm的方法如下:

1.在程式開頭處標上一個label。
2.在每個呼叫自己的敘述的下一個敘述前，各標上一個label。
3.把每個呼叫自己的敘述代換成一個將目前狀態push到stack的敘述，以及將程式參數改變的敘述，然後跳回程式的開頭。
4.將每個返回敘述變成檢查stack的敘述，只有在stack為空時才能返回，否則必須pop出以前的狀態，然後跳到應返回的位置繼續執行。

上述的方法其實是在模擬程序遞迴呼叫的方式，label的記錄則是要得知其返回位址。因此本題的non-recursive algorithm便可以化成:

Procedure HANOI(A,B,C,n) // 將n個環從A移到B //
step 1:
if n<=0 then
print("error")
else if n=1 then
print(A,"→",B)
else
[ push(A,B,C,n-1,2);
(A,B,C,n)←(A,C,B,n-1);
goto step 1;
step 2:
print(A,"→",B);
push(A,B,C,n-1,3);
(A,B,C,n)←(C,B,A,n-1);
goto step 1; ]
step 3:
if stack not empty then
[ pop(A,B,C,n,ret_step);
goto ret_step ]
end

這個方法所得出的algorithm雖然不是最佳的，但是卻保證一定正確。當然您也可以利用程式技巧將它化簡成沒有label的結構化程式。另外一種方式是要靠靈感的，可說是可遇而不可求。例如上述algorithm，其實可以寫成:

Procedure HANOI（A,B,C,n) // 將n個環從A移到B //
step 1:
if n<=0 then
print("error")
else if n=1 then
print(A,"→",B)
else
[ Push(C,B,A,n-1);
Push(A,B,C,1);
Push(A,C,B,n-1) ]
if stack not empty then
[ pop（A,B,C,n);
goto step 1 ]
end

使用三個push敘述來模擬三次搬運，相當簡潔。這是從觀察它的呼叫方式和stack的關係所發覺的，並無規則可循。雖然這個algorithm相當簡潔，但是執行速度並不是最好的。主要的原因是在於模擬recursice call的stack push和pop次數太多，因而減低了執行的速度。如果我們所要求的是速度的話，則必須儘量不要用stack的結構來模擬，應該從分析該問題non-recursive關係著手。這種過程一般都相當冗煩，而且不一定能夠做得到。這裡我們只列舉別人研究的成果供讀者參考，並做為以後您將來寫程式時的一個目標。Hanoi塔問題的non-recursive關係如下:

另類行列式計算法——Chiò 演算法

另類行列式計算法——Chiò 演算法
http://ccjou.twbbs.org/blog/?p=4513

2011年6月16日星期四

爱丽丝的发丝──《爱丽丝惊魂记：疯狂再临》制作点滴

爱丽丝的发丝──《爱丽丝惊魂记：疯狂再临》制作点滴
http://www.cnblogs.com/miloyip/archive/2011/06/14/alice_madness_returns_hair.html

2011年5月18日星期三

Bellard's formula for pi

Bellard's formula
http://en.wikipedia.org/wiki/Bellard%27s_formula
算pi最快

Bellard's formula, as used by PiHex, the now-completed distributed computing project, is used to calculate the nth digit of π in base 2. It is a faster version (about 43% faster[1]) of the Bailey–Borwein–Plouffe formula. Bellard's formula was discovered by Fabrice Bellard in 1997.

計算的威力，智慧的傳奇—— Fabrice Bellard

計算的威力，智慧的傳奇—— Fabrice Bellard
http://www.hksilicon.com/kb/articles/5760/Fabrice-Bellard

http://en.wikipedia.org/wiki/Fabrice_Bellard

In 1997, he discovered the fastest formula to calculate single digits of pi in binary representation, known as Bellard's formula. It is a variant of the Bailey-Borwein-Plouffe formula.[1]

算pi最快!!

In the year 2000 edition[3] in the category "Most specific output" for a program that implements the modular Fast Fourier Transform and innovatively uses it to compute the then biggest known prime number, 2^6972593-1[4]

為啥富利葉轉換與質數有關?

2011年5月8日星期日

點空間 Dot.Space

http://www.dotspace.idv.tw

2011年4月22日星期五

Regular Expression Application (1)

Regular Expression Application (1)
http://godspeedlee.myweb.hinet.net/regex/1/num_range.htm

2011年4月9日星期六

C++箴言：在operator= 中處理自賦值

C++箴言：在operator= 中處理自賦值
http://www.builder.com.cn/2007/1027/585438.shtml

w = w;
自賦值安全（self-assignment-safe）
異常安全（exception-safe）

=================================================================
Widget&
Widget::operator=(const Widget& rhs) // unsafe impl. of operator=
{
delete pb; // stop using current bitmap
pb = new Bitmap(*rhs.pb); // start using a copy of rhs's bitmap

return *this; // see Item 10
}

class Widget {
...　
void swap(Widget& rhs); // exchange *this's and rhs's data;
... // see Item 29 for details
};

================================================================
Widget& Widget::operator=(const Widget& rhs)
{
Widget temp(rhs); // make a copy of rhs's data

swap(temp); // swap *this's data with the copy's
return *this;
}