動態迷宮建立 (C語言)

//===============================================================
// 20090522/28 知識 +
// http://tw.knowledge.yahoo.com/question/question?qid=1509052205422
// http://tw.knowledge.yahoo.com/question/question?qid=1609052807673
// 發問者 :(wsx01 ) http://tw.knowledge.yahoo.com/my/my?show=AC04892662
//===============================================================

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

char *maze;
int m_Col, m_Row;
int m_Start, m_End;
int m_Size;

//顯示迷宮
void ShowMaze()
{             //  空地  路徑  牆壁
  char *sym[] = { "　", "◇", "█" };
  for(int i=0; i<m_Size; )
  {
     printf( "%s", sym[maze[i]]);
     if(++i%m_Col==0) printf("\n");
  }
}
//路徑尋找: 回傳由[b]到[e]的路徑數量
int Visit(int b, int e, int s)
{ // s!=0 有路徑時顯示
  int n=1;
  if (maze[b]!=0) return 0;
  maze[b] = 1;    //設定為走過的地方
  if (b!=e)
    n = Visit(b+1,e,s)+ Visit(b+m_Col,e,s)+ Visit(b-1,e,s) + Visit(b-m_Col,e,s);
  else if (s) ShowMaze(); //有路徑 n=1;
  maze[b] = 0;
  return n;
}
// 建立迷宮
int CreateMaze(int row, int col)
{
  int r, c, p, m, n, i;
  m_Row = (row<4)? 4: row;
  m_Col = (col<4)? 4: col;
  m_Size = m_Row*m_Col;
  maze = (char *) malloc(sizeof(char)*m_Size); // 配置記憶體
  if (maze==NULL) return 0;
  for(i=0; i<m_Size; i++) maze[i] = 2;
  maze[ m_Start=m_Col+1 ] = 0;
  maze[ m_End=m_Col*(m_Row-1)-2 ] = 0;

  p = (m_Col-2)*(m_Row-2);
  while(Visit(m_Start, m_End, 0 )!=1 || p>0 )
  {
    r = rand()%(m_Row-2)+1;
    c = rand()%(m_Col-2)+1;
    i = r*m_Col+c;
    if (maze[i]==0) continue;  // 已經是空地了
     maze[i]=0;
    m = Visit(i, m_Start, 0);  //連接起點路徑數量
     n = Visit(i, m_End, 0 );   //連接終點路徑數量
     p = (m==1 && n==1)? (m_Col-2)*(m_Row-2): p-1;
    if ((m==1 && n<2) || (n==1 && m<2) ) continue;
    maze[i]=2;
  }
  return 1;
}
// === 主程式 ===
int main()
{
  int r, c;
  srand((unsigned)time(NULL));
  while(1)
  {
    printf("\n 請輸入迷宮大小(行Column與列Row兩個數目,負值離開):");
    if (scanf("%d", &c)!=1 || c<0 || scanf("%d", &r)!=1 || r<0) break;
    if (!CreateMaze(r,c)) break;   // 設定迷宮大小 (失敗離開)
    Visit(m_Start, m_End, 1 );
    free(maze);  // 釋放記憶體
  }
  system("pause");
  return 0;
}
//====

Heap實作 -- MaxHeap, MinHeap, HeapSort (C語言)

//===============================================================
// 20090512~20 知識 +
// http://knowledge.yahoo.com.tw/question/question?qid=1009051205898
// http://knowledge.yahoo.com.tw/question/question?qid=1509051812541
// http://knowledge.yahoo.com.tw/question/question?qid=1509051900001
// http://knowledge.yahoo.com.tw/question/question?qid=1009052007512
// 發問者 :(小卓 ) http://tw.knowledge.yahoo.com/my/my?show=AE03871682
//===============================================================

下面程式已修改適用於 MaxHeap, MinHeap, 並增加 HeapSort......
主程式內有一些應用範例, 可供參考...

#include <stdio.h>
#include <stdlib.h>

#define  Comp(A,B) ((heapMode==MINHEAP)?(A<B):(A>B))
const int Max = 32;
const int MAXHEAP = 2;
const int MINHEAP = 1;
int heap[Max+1]; 
int heapSize=0;    
int heapMode = 0;
void Heap_init(int);

// 上升
int HeapUp(int i, int mode=0)
{
  if (heapMode==0 || (heapMode!=mode && mode!=0)) Heap_init(mode);
  int y = heap[i];
  for (int c=i/2; c>0 && Comp(y,heap[c]); c/=2)
  {
    heap[i] = heap[c];
    i = c;             
  }
  heap[i] = y;  
  return i;
}
// 下降
int HeapDown(int i, int mode=0)
{
  if (heapMode==0 || (heapMode!=mode && mode!=0)) Heap_init(mode);
  int y = heap[i];
  for (int c = 2*i; c <= heapSize; c*=2)
  {
    if (c < heapSize && Comp(heap[c+1],heap[c])) c++;
    if (Comp(y,heap[c])) break; 
    heap[i] = heap[c];
    i = c;
  }
  heap[i] = y;  
  return i;
}
// 調整為 Heap
void Heap_init(int mode=0)
{
  if (mode==0 && heapMode==0) heapMode=MAXHEAP;
  else if(mode!=0) heapMode = mode;  
  for (int i = heapSize/2; i >= 1; i--)
     HeapDown(i);
}
// 插入
int Heap_insert(int d, int mode=0) 
{
  if (heapMode==0 || (heapMode!=mode && mode!=0)) Heap_init(mode);
  if (heapSize == Max) return 0;
  heap[++heapSize]=d;
  return HeapUp(heapSize);
}
// 刪除
int Heap_delete(int d, int mode=0)
{
  if (heapMode==0 || (heapMode!=mode && mode!=0)) Heap_init(mode);
  for(int i=1; i<=heapSize; i++)
     if ( heap[i]==d )
     {
        heap[i] = heap[heapSize--];
        if (i==HeapUp(i)) HeapDown(i);
        return i;
     }
  return -1;
}
// 排序 -- 交換
void swap(int *i, int *j) { int t=*i; *i = *j; *j = t; }
// 排序
void Heap_sort(int mode=0)
{
   if (heapMode==0 || (heapMode!=mode && mode!=0)) Heap_init(mode);
   int size = heapSize;
   while (heapSize>1)
   {
      swap(&heap[1], &heap[heapSize--]);
      HeapDown(1);
   }
   for(int k=size; heapSize<k; k--)
      swap(&heap[heapSize++], &heap[k]);
   heapSize = size;
}
// 以樹狀顯示
void ShowTree(char *t) 
{
  int p=1;
  while(p<=heapSize) p*=2;
  printf( "%s\n%*s", t, --p, "");
  for(int i=1, n=1; i<=heapSize; i++, n=p*2-1)
  {
    printf( "%3d%*s", heap[i], n, "");
    if (!(i&(i+1))) printf ("\n%*s", p=(p-1)/2, "");
  }
  printf ("\n");
}
// 主程式 ===
int main()
{
  int A[] = { 15, 23, 10, 40, 30 }; 
  int B[] = { 20, 30, 10, 50, 60, 40, 45, 5 };
  int i, sizeA = sizeof(A)/sizeof(int), sizeB = sizeof(B)/sizeof(int);
  // -- 由 A陣列資料為二元樹, 調整為 MaxHeap
  for(i=0, heapSize=sizeA; i<sizeA; i++) heap[i+1]=A[i];
  ShowTree("\n\n(A.1) 顯示調整前 二元樹:"); 
  Heap_init();
  ShowTree("\n      顯示調整後 MaxHeap:"); 
  //    再調整為 MinHeap 並排序
  //Heap_init(MINHEAP);
  Heap_sort(MINHEAP);
  ShowTree("\n      顯示Sort後 MinHeap:"); 
  // -- 由 B陣列資料為二元樹, 調整為 MaxHeap
  for(i=0, heapSize=sizeB; i<sizeB; i++) heap[i+1]=B[i];
  ShowTree("\n\n(B.1) 顯示調整前 二元樹:"); 
  Heap_init(MAXHEAP);
  ShowTree("\n      顯示調整後 MaxHeap:");
  //    再刪除兩筆資料
  Heap_delete(30);
  Heap_delete(60);
  ShowTree("\n\n(B.2) 刪除了 30 60 後 MaxHeap:");
  // -- 由 B陣列資料建立 MinHeap
  for(i=0, heapSize=0; i<sizeB; i++)
      Heap_insert(B[i], MINHEAP); 
  ShowTree("\n\n(B.3) 由資料所建立的 MinHeap :"); 
  //    再刪除兩筆資料
  Heap_delete(10);
  Heap_delete(30);
  ShowTree("\n\n(B.4) 刪除了 10 30 後 MinHeap:");
  //    再增加 55 並調整為 MaxHeap
  Heap_insert(55, MAXHEAP);
  Heap_insert(35);
  ShowTree("\n\n(B.5) 調整為 MaxHeap 並增加 55 35:");
  Heap_sort();
  ShowTree("\n\n(B.6) 排序後的 MaxHeap:"); 
  system("pause");
  return 0;
}
//===============================================

【執行結果】 :

(A.1) 顯示調整前 二元樹:
        15
    23      10
  40  30

      顯示調整後 MaxHeap:
        40
    30      10
  23  15

      顯示Sort後 MinHeap:
        10
    15      23
  30  40


(B.1) 顯示調整前 二元樹:
                20
        30              10
    50      60      40      45
   5

      顯示調整後 MaxHeap:
                60
        50              45
    20      30      40      10
   5


(B.2) 刪除了 30 60 後 MaxHeap:
        50
    20      45
  10   5  40


(B.3) 由資料所建立的 MinHeap :
                 5
        10              20
    30      60      40      45
  50


(B.4) 刪除了 10 30 後 MinHeap:
         5
    45      20
  50  60  40


(B.5) 調整為 MaxHeap 並增加 55 35:
                60
        50              55
    35      45      20      40
   5


(B.6) 排序後的 MaxHeap:
                60
        55              50
    45      40      35      20
   5

身分證號檢查 (C)

//===============================================================
// 20090527 知識 +
// http://tw.knowledge.yahoo.com/question/question?qid=1609052704838
// 發問者 :(天鱗 ) http://tw.knowledge.yahoo.com/my/my?show=AA01112269
//===============================================================

#include <stdio.h>
#include <stdlib.h>
// 檢查身分證號檢查碼
int verify(char * a)
{          //-   A/N B/O C/P D/Q E/R F/S G/T H/U I/V J/W K/X L/Y M/Z
  char IDC[] = { 10, 11, 12, 13, 14, 15, 16, 17, 34, 18, 19, 20, 21,
                 22, 35, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33 };
  int i, chk = IDC[(a[0]&0xDF)-'A'];
  chk = chk/10+chk%10*9;
  for(i=1; i<9; i++)
    chk += (a[i]&0x0F)*(9-i);
  if (a[i]=='?') return chk;
  return (chk+(a[i]&0x0F))%10==0;   
}
// 檢查身分證號格式
int CheckID(char *id)
{
  int i = 0;
  while(id[i]!=0) i++;
  if (i!=10) return -2;
  int num = (id[0]&0xDF)-'A';
  if (num<0 || num>25) return -3;
  for(i=1; i<=9; i++)
    if(id[i]<'0' || id[i]>'9')
       if(i!=9 || id[i]!='?') return -4;  
  i = verify(id);
  return  i? i: -1;
}
// 檢查身分證號與顯示
int CheckShow(char *id)
{
  char *msg[] = { "正確!", "不正確!", "字數不對!", "字首應為A~Z!", "字身應為0~9" };
  int ret = CheckID(id);
  if (ret>1) printf( "-- 檢查碼為 %d\n", (1000-ret)%10);
  else printf( "--- %s\n", (ret<0)? msg[ret*-1]: msg[0]);
  return (ret<0)? ret: 0;
}
// 主程式 ---
int main(int argc, char *argv[])
{
  int ret=0;
  if (argc>1)
    for(int i=1; i<argc; ret=CheckShow(argv[i++]))
        printf( "身分證號 : %s   ", argv[i]);
  else
    while(!fflush(stdin))
    {        
      char inp[12];
      printf("\n請輸入身分證號(只輸入一個字將結束程式): ");
      if (scanf("%s", inp)!=1) continue;
      if (inp[1]=='\0') break;
      CheckShow(inp);
    }
  system("pause");
  return ret;
}
// ---------------------------------------

循環式質數 (c/c++)

//===============================================================
// 20090521 知識 +
// http://tw.knowledge.yahoo.com/question/question?qid=1009052111388
// 發問者 :(兔〞ｍａｎ〃 ) http://tw.knowledge.yahoo.com/my/my?show=AB01282140
//===============================================================

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>

const int _max = 100000;    // 質數表大小
int prime[_max] = { 2, 3, 5, 7, 11 };
int _lx;
// --- 建立質數表
void initPrime()
{
  int p, x=4, i=5;
  for(int n=13; i<_max; n+=x, x=6-x)
  {
     int q = (int)sqrt((double)n);
     for(p=1; p<i && prime[p]<=q; p++)
        if (n%prime[p]==0) p=i;
     if (p<i) prime[i++] = n;
  }
  _lx = 6-x;
  return;
}
// --- 檢查是否為質數
bool IsPrime(long long num)
{
  int i = (int)(num%6);
  if (num>6 && i!=1 && i!=5) return false;
  long q = (long) sqrt((long double)num);
  for(i=2; i<_max && prime[i]<=q; i++)
     if (num%prime[i]==0) return false;
  if (i<_max) return true;
  long n = prime[_max-1]+_lx;
  for(i=_lx ;n<=q; n+=i, i=6-i)
     if (num%n==0) return false;
  return true;
}
// --- 指定位數的循環式質數檢查
char d[4] = { 1, 3, 7, 9 };
char a[16];
void checkN(int n)
{
  printf( "\n %d 位數:", n );
  int i, m, c, l, o=1, max = 1;
  for(i=0; i<n; i++) { max*=4; o*=10; }
  for(l=0, o/=10; l<max; l++)
  {
     for(i=n-1, m=l; i>=0; i--, m/=4) a[i]=d[m%4];
     for(i=0, c=0; i<n; i++) c=c*10+a[i];
     for(i=0, m=c; i<n; i++, m=m/10+m%10*o)
        if (!IsPrime(m)) break;
     if (i==n) printf( " %d", c );
  }
  printf("\n");
}
// --- 檢查是否為循環式質數
bool checkNum(int c)
{
  int m, n, o, i;
  for(m=c, n=0; m>0; m/=10) n++;   // 計算位數
  // if (n<2 || n>8 ) return false;
  for(i=1, o=1; i<n; i++) o*=10;   // 偏移值
  for(i=0, m=c; i<n; i++, m=m/10+m%10*o)  //循環
     if (!IsPrime(m)) return false;
  return true;
}
// =========== 主程式 ============
int main()
{
  clock_t start = clock();
  initPrime();
  clock_t begin = clock();
  printf( "\n循環式質數 總覽 -- \n");
  for(int nn=2; nn<9; nn++) checkN(nn);
  clock_t end = clock();
  printf( "\n總計時間: %.3fsec.  質數表建立時間: %.3fsec.  處理時間: %.3fsec.\n\n",
          (double)(end-start)/CLOCKS_PER_SEC, (double)(end-begin)/CLOCKS_PER_SEC,
          (double)(begin-start)/CLOCKS_PER_SEC );
  //------------
  int d;
  while(1)
  {
     printf("\n請輸入一個2~9位數值, 將檢測其是否為循環式質數 :");
     if (scanf("%d", &d)!=1 || d<10 || d>999999999) break;
     if (checkNum(d)) printf("○ %d是一個循環式質數!!\n", d);
     else  printf("╳ %d不是一個循環式質數!!\n", d);
  }
  return 0;
}
//====================================================