Get Max Subsequence

留下评论

/*
 *Gets the special sub sequence whose items’ sum is max among all the sub sequences for the given sequenc.
 *sequence: the given sequence;
 * length: the length of the given sequence;
 * return value: the sum of the elements in the special sub sequence.
 */
int GetMaxSubsequence(int sequence[], int length)
{
 int start = 0, end = 0;
 int sum = 0;
 int max = 0;
 for(int i = 0; i < length; i++)
 {
  sum += sequence[i];
  if(sum > 0)
  {
   if(max == 0)
   {
    start = i;
   }
   if(sum > max)
   {
    max = sum;
    end = i;
   }
  }
  else
  {
   sum = 0;
   max = 0;
  }
 }
 cout << "start = " << start << endl;
 cout << "end = " << end << endl;
 return max;
}

Power set

一条评论

#include <stdio.h>
#include <stdlib.h>
int count = 0;
typedef struct ListNode
{
    int Data;
    struct ListNode *Next;
} ListNode;
void ListInsert(ListNode* list, int insertedIndex, int data)
{
    ListNode *tempNode = (ListNode*)malloc(sizeof(ListNode));
   
    ListNode *tempHead = list;
    if(tempNode != NULL)
    {
        tempNode->Data = data;
        tempNode->Next = NULL;
        int i = 0;
        while(i++ < insertedIndex && tempHead != NULL)
        {
            tempHead = tempHead->Next;
        }
        ListNode * tempNext = tempHead->Next;
        tempHead->Next = tempNode;
        if(tempNext != NULL)
        {
            tempNode->Next = tempNext;
        }
    }
}
void ListDelete(ListNode *list, int deletedIndex, int data)
{  
    ListNode *tempHead = list;
    int i = 0;
    while(i++ < deletedIndex && tempHead != NULL)
    {
        tempHead = tempHead->Next;
    }
    if(tempHead->Next != NULL)
    {
        ListNode *tempNode2 = tempHead->Next;
        ListNode *tempNode1 = tempNode2->Next;
        tempHead->Next = tempNode1;
        free(tempNode2);
    }
}
void Output(ListNode *list)
{
    ListNode *tempNode = list->Next;
    while(tempNode)
    {
        if(tempNode->Next == NULL)
        {
            printf("%d;\n", tempNode->Data);
        }
        else
        {
            printf("%d,", tempNode->Data);
        }
        tempNode = tempNode->Next;
    }
}
int ListLength(ListNode *list)
{
    int i = 0;
    ListNode *tempNode = list->Next;
    while(tempNode)
    {
        tempNode = tempNode->Next;
        i++;
    }
    return i;
}
int GetElem(ListNode *list, int index)
{
    ListNode *tempNode = list->Next;
    int i = 0;
    while(tempNode && i++ < index)
    {
        tempNode = tempNode->Next;
    }
    if(i – 1 == index)
    {
        return tempNode->Data;
    }
    else
    {
        return -1;
    }
}
void GetPowerSet(int i, ListNode *A, ListNode *B)
{
    if(i >= ListLength(A))
    {
        count++;
        Output(B);
        //FreeList(B);
    }
    else
    {
        int x = GetElem(A, i);
        int k = ListLength(B);
        ListInsert(B, k – 1, x);
        GetPowerSet(i + 1, A, B);
        ListDelete(B, k – 1, x);
        GetPowerSet(i + 1, A, B);
    }
}
FreeList(ListNode *B)
{
    ListNode *tempNode = B->Next;
    while(tempNode)
    {
        ListNode *temp = tempNode->Next;
        free(tempNode);
        tempNode = temp;
    }
    B->Next = NULL;
}
int main(int argc, char *argv[])
{
  ListNode *A = (ListNode*)malloc(sizeof(ListNode));
  A->Data = -1;
  A->Next = NULL;
  int i = 0;
  for(; i < 5; i++)
  {
    ListInsert(A, i, i+1);       
  }
  //Output(A);
  ListNode *B = (ListNode*)malloc(sizeof(ListNode));
  B->Data = -1;
  B->Next = NULL;
  //Output(B);
  GetPowerSet(0, A, B);
  printf("The totoal count is : %d\n", count);
  FreeList(A);
  FreeList(B);
  system("PAUSE"); 
  return 0;
}

Color problem

留下评论

#include <stdio.h>
#include <stdlib.h>
#define ROW 4
#define COL 4
#define NUM 4
int src[ROW][COL];
int colored[ROW];
int color[NUM];
int coloredIndex;
int count1 = 0;
int count2 = 0;
void Intialize()
{
    int i, j;
    for(i = 0; i < ROW; i++)
    {
        for(j = 0; j < COL; j++)
        {
            src[i][j] = 0;
        }
    }
    src[0][1] = 1;
    src[1][0] = 1;
    src[0][2] = 1;
    src[2][0] = 1;
    src[1][3] = 1;
    src[3][1] = 1;   
    src[1][2] = 1;
    src[2][1] = 1;   
    src[2][3] = 1;
    src[3][2] = 1;   
    for(i = 0; i < NUM; i++)
    {
        color[i] = i;
    }
    coloredIndex = -1;
    for(i = 0; i < ROW; i++)
    {
        colored[i] = -1;
    }
}
int Check(int row)
{
    int j;
    for(j = 0; j < row; j++)
    {
        if(colored[j] > -1 && src[row][j] && colored[j] == colored[row])
        {
            break;
        }
    }
    if(j >= row)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
void Color(int row)
{
    if(row == ROW)
    {
        // Get a solution
        count1++;
        int k;
        for(k = 0; k < row; k++)
        {
            switch(colored[k])
            {
            case 0:
                printf("r");
                break;
            case 1:
                printf("w");
                break;
            case 2:
                printf("b");
                break;
            case 3:
                printf("y");
                break;
            }
        }
        printf("\n");
    }
    else
    {
        int index;
        for(index = 0; index < NUM; index++)
        {
            colored[row] = index;
            if(Check(row))
            {
                Color(row+1);
            }
            else
            {
                colored[row] = -1;
            }
        }
    }
}
void ColorWithNoRecursion()
{
    int colorIndex = 0;
    while(1)
    {
        for(colorIndex = colored[coloredIndex] + 1;colorIndex < NUM;colorIndex++)
        {
            colored[coloredIndex] = colorIndex;
            if(Check(coloredIndex))
            {
                break;
            }
        }
        if(colorIndex == NUM)
        {
            if(coloredIndex == 0)
            {
                printf("\nsuccess\n");
                break;
            }
            colored[coloredIndex] = -1;
            coloredIndex–;
        }
        else
        {
            coloredIndex++;
            if(coloredIndex == ROW)
            {
                count2++;
                int k;
                for(k = 0; k < coloredIndex; k++)
                {
                    switch(colored[k])
                    {
                    case 0:
                        printf("r");
                        break;
                    case 1:
                        printf("w");
                        break;
                    case 2:
                        printf("b");
                        break;
                    case 3:
                        printf("y");
                        break;
                    }
                }
                printf("\n");
                coloredIndex = ROW – 1;
            }
            else
            {
                colored[coloredIndex] = -1;
            }
        }
    }
}
int main(int argc, char *argv[])
{
  Intialize();
  Color(0);
  printf("\n%d\n", count1);
  //ColorWithNoRecursion();
  //printf("\n%d\n", count2);
  system("PAUSE"); 
  return 0;
}

Eight queens

留下评论

#include <stdio.h>
#include <stdlib.h>
int IsSafe(int col, int row, int queenList[])
{
    int tempCol = 0;
    for(tempCol; tempCol < col; tempCol++)
    {
        int tempRow = queenList[tempCol];
        if(tempRow == row)
        {
            return 0;
        }
        if(tempCol == col)
        {
            return 0;
        }
       
        if(tempRow – tempCol == row – col ||
           tempRow + tempCol == row + col)
        {
            return 0;
        }
    }
    return 1;
}
int PlaceQueen(int queenList[], int col)
{
    int row = 0;
    int foundSafePos = 0;
    if(col == 8)
    {
        foundSafePos = 1;
    }
    else
    {
        while(row < 8 && !foundSafePos)
        {
            if(IsSafe(col, row, queenList))
            {
                queenList[col] = row;
                foundSafePos = PlaceQueen(queenList, col + 1);
                if(!foundSafePos)
                {
                    row++;
                }
            }
            else
            {
                row++;
            }
        }
    }
    return foundSafePos;
}
#define SIZE 8
int count = 0;
void EightQueenNoRecursion(int queen[])
{
    int y,x,i,j,d,t;
    y = 0;
    queen[0] = -1;
    while(1)
    {
        for(x = queen[y] + 1; x < SIZE; x++)
        {
            for(i = 0; i < y; i++)
            {
                j = queen[i];
                d = y – i;
                // Checks whether the new queen attacks others.
                if(j == x ||
                   j == x – d ||
                   j == x + d)
                {
                    break;
                }
            }
            if(i >= y)
            {
                // no attack
                break;
            }
        }
        if(x == SIZE)
        {
            if(0 == y)
            {
                // Back to the first line
                printf("Done");
                // Over
                break;
            }
           
            // Back
            queen[y] = -1;
            y–;
        }
        else
        {
            queen[y] = x;
            y++;
            if(y < SIZE)
            {
                queen[y] = -1;
            }
            else
            {
                printf("\n");
                count++;
                for(i = 0; i < SIZE; i++)
                {
                    for(j = 0; j < SIZE; j++)
                    {
                        if(queen[i] == j)
                        {
                            printf("q");
                        }
                        else
                        {
                            printf("*");
                        }
                    }
                    printf("\n");
                }
                // Back
                y = SIZE – 1;
            }
        }
    }
}
/*
int main(int argc, char *argv[])
{
    int queen[SIZE];
    int i;
    for(i = 0; i < SIZE; i++)
    {
        queen[i] = 0;
    }
    EightQueenNoRecursion(queen);
    printf("The total count is : %d\n", count);
  system("PAUSE");
    return 0;
}*/
/*
int main(int argc, char *argv[])
{
    printf("Start*********************\n");
    int b[8] = {0, 1, 2, 3, 4, 5, 6, 7};
    int sum = 0;
    while(b[0] < 8)
    {
        int j;
        for(j = 7; j >= 0; j–)
        {
            if(j && b[j] < 7)
            {
                b[j]++;
                break;
            }
            else if(!j)
            {
                b[j]++;
                break;
            }
            else
            {
                b[j] = 0;
            }
        }
        for(j = 0; j < 7; j++)
        {
            int k;
            for(k = j + 1; k < 8; k++)
            {
                if(b[j] == b[k] ||
                j + b[j] == k + b[k] ||
                j – b[j] == k – b[k])
                {
                    j = 8;
                    k = 8;
                }
                else if(j == 6)
                {
                    sum++;
                    char c = ‘A’;
                    int a;
                    for(a = 0; a < 8; a++)
                    {
                        printf("%d%d ", c++, b[a] + 1);
                    }
                    printf("\n");
                    j = 8;
                    k = 8;
                }
            }
        }
    }
    system("PAUSE");
    return 0;
}
*/
/*
int main(int argc, char *argv[])
{
  int queenList[8] = {0, 0, 0, 0, 0, 0, 0, 0};
  int j;
  for(j = 0; j < 8; j++)
  {
       queenList[0] = j;
       int res = PlaceQueen(queenList, 1);
      
       if(res)
       {
            printf("    ");
            int i;
            for(i = 0; i < 8; i++)
            {
                printf("\n");
                int a;
                for(a = 0; a < 8; a++)
                {
                    if(i == queenList[a])
                    {
                        printf(" q ");
                    }
                    else
                    {
                        printf(" * ");
                    }
                }
            }
            printf("\n");
       }
       else
       {
           printf("Can’t complete the chess");
       }
  }
  system("PAUSE"); 
  return 0;
}
*/

Get changes

留下评论

#include <stdio.h>
#include <stdlib.h>
int M[] = {1, 2, 5, 10, 20, 50, 100};
//int M[] = {100, 50, 20, 10, 5, 2, 1};
int N = 7;
void Find(int money, int index, int num[])
{
    if(money >= M[index])
    {
        num[index]++;
        money -= M[index];
        if(money == 0)
        {
            int j;
            for(j = 0; j < N; j++)
            {
                printf("%d:%d; ", M[j], num[j]);
            }
            printf("\n");
        }
        else
        {
            Find(money, index, num);
        }
        if(index + 1 < N)
        {
            num[index]–;
            money += M[index];
            Find(money, index + 1, num);
        }
        else
        {
            num[N – 1] = 0;
        }
    }
    else
    {
        if(index + 1 < N)
        {
            Find(money, index + 1, num);
        }
    }
}
int main(int argc, char *argv[])
{
  int num[] = {0, 0, 0, 0, 0, 0, 0};
  Find(100, 0, num);
  system("PAUSE");
  return 0;
}