Monday, November 17, 2014

Print Matrix Diagonally

Given a 2D matrix, print all elements of the given matrix in diagonal order. For example, consider the following 5 X 4 input matrix.
    1     2     3     4
    5     6     7     8
    9    10    11    12
   13    14    15    16
   17    18    19    20  (5x4)
Diagonal printing of the above matrix is
    1
    5     2
    9     6     3
   13    10     7     4
   17    14    11     8
   18    15    12
   19    16
   20
Following is C++ code for diagonal printing.
The diagonal printing of a given matrix ‘matrix[ROW][COL]‘ always has ‘ROW + COL – 1′ lines in output
#include <stdio.h>
#include <stdlib.h>
 
#define ROW 5
#define COL 4
 

int min(int a, int b)
{ return (a < b)? a: b; }
 
int min(int a, int b, int c)
{ return min(min(a, b), c);}
 

int max(int a, int b)
{ return (a > b)? a: b; }
 

void diagonalOrder(int matrix[][COL])
{
    for (int line=1; line<=(ROW + COL -1); line++)
    {
        /* Get column index of the first element in this line of output.
The index is 0 for first ROW lines and line - ROW for remaining
           lines  */
        int start_col =  max(0, line-ROW);
 
        /* Get count of elements in this line. The count of elements is
           equal to minimum of line number, COL-start_col and ROW */
         int count = min(line, (COL-start_col), ROW);
        for (int j=0; j<count; j++)
            printf("%5d ", matrix[min(ROW, line)-j-1][start_col+j]);
 
        /* Ptint elements of next diagonal on next line */
        printf("\n");
    }
}
 

void printMatrix(int matrix[ROW][COL])
{
    for (int i=0; i< ROW; i++)
    {
        for (int j=0; j<COL; j++)
            printf("%5d ", matrix[i][j]);
        printf("\n");
    }
}
 
int main()
{
    int M[ROW][COL] = {{1, 2, 3, 4},
                       {5, 6, 7, 8},
                       {9, 10, 11, 12},
                       {13, 14, 15, 16},
                       {17, 18, 19, 20},
                      };
    printf ("Given matrix is \n");
    printMatrix(M);
 
    printf ("\nDiagonal printing of matrix is \n");
    diagonalOrder(M);
    return 0;
}

DP -- Minimal coins problem

  1. public class CoinsChange {  
  2.     /**  
  3.      * 硬币找零:动态规划算法  
  4.      *   
  5.      * @param values  
  6.      *            :保存每一种硬币的币值的数组  
  7.      * @param valueKinds  
  8.      *            :币值不同的硬币种类数量,即coinValue[]数组的大小  
  9.      * @param money  
  10.      *            :需要找零的面值  
  11.      * @param coinsUsed  
  12.      *            :保存面值为i的纸币找零所需的最小硬币数  
  13.      */ 
  14.     public static void makeChange(int[] values, int valueKinds, int money,  
  15.             int[] coinsUsed) {  
  16.  
  17.         coinsUsed[0] = 0;  
  18.         // 对每一分钱都找零,即保存子问题的解以备用,即填表  
  19.         for (int cents = 1; cents <= money; cents++) {  
  20.  
  21.             // 当用最小币值的硬币找零时,所需硬币数量最多  
  22.             int minCoins = cents;  
  23.  
  24.             // 遍历每一种面值的硬币,看是否可作为找零的其中之一  
  25.             for (int kind = 0; kind < valueKinds; kind++) {               
  26.                 // 若当前面值的硬币小于当前的cents则分解问题并查表  
  27.                 if (values[kind] <= cents) {  
  28.                     int temp = coinsUsed[cents - values[kind]] + 1;  
  29.                     if (temp < minCoins) {  
  30.                         minCoins = temp;  
  31.                     }  
  32.                 }  
  33.             }  
  34.             // 保存最小硬币数  
  35.             coinsUsed[cents] = minCoins;  
  36.  
  37.             System.out.println("面值为 " + (cents) + " 的最小硬币数 : " 
  38.                     + coinsUsed[cents]);  
  39.         }  
  40.     }  
  41.       
  42.     public static void main(String[] args) {  
  43.  
  44.         // 硬币面值预先已经按降序排列  
  45.         int[] coinValue = new int[] { 25, 21, 10, 5, 1 };  
  46.         // 需要找零的面值  
  47.         int money = 63;  
  48.         // 保存每一个面值找零所需的最小硬币数,0号单元舍弃不用,所以要多加1  
  49.         int[] coinsUsed = new int[money + 1];  
  50.  
  51.         makeChange(coinValue, coinValue.length, money, coinsUsed);  
  52.     }  
  53. } 
测试结果:
面值为 1 的最小硬币数 : 1
面值为 2 的最小硬币数 : 2
面值为 3 的最小硬币数 : 3
面值为 4 的最小硬币数 : 4
面值为 5 的最小硬币数 : 1
面值为 6 的最小硬币数 : 2
...
...
面值为 60 的最小硬币数 : 3
面值为 61 的最小硬币数 : 4
面值为 62 的最小硬币数 : 4
面值为 63 的最小硬币数 : 3