m[0][0]에서 m[3][3]까지 가는데 합이 가장 큰 길은??

M배열에 자기 까지의 최고 합을 메모한다.

 

m배열

 6

12 

 5

 5

11 

 18

 7

 17

3

 3

 8

 10

14

 9

 

 #include <stdio.h>
#include <stdlib.h>
 
int matrixPath(int m[][4], int r, int c, int i, int j, int M[][4])
{
    if (i == 0 && j == 0)
    {
        printf("m[%d][%d] :%d  \n", i, j, m[i][j]);
        return m[i][j];
    }
    else if (i == 0)
    {
        if (M[0][j] == 0)
            M[0][j] = matrixPath(m, r, c, 0, j - 1, M) + m[i][j];
        printf("M[%d][%d] :%d  \n", i, j, M[i][j]);
 
        return M[0][j];
 
    }
    else if (j == 0)
    {
        if (M[i][0] == 0)
            M[i][0] = matrixPath(m, r, c, i - 1, 0, M) + m[i][j];
        printf("M[%d][%d] :%d  \n", i, j, M[i][j]);
       
        return M[i][0];
 
    }
    else
    {
        int a, b;
        if (M[i - 1][j] == 0)
            M[i - 1][j] = matrixPath(m, r, c, i - 1, j, M);
        if (M[i][j - 1] == 0)
            M[i][j - 1] = matrixPath(m, r, c, i, j - 1, M);
        a = M[i - 1][j];
        b = M[i][j - 1];
        printf("M[%d][%d] :%d , M[%d][%d]: %d \n",i-1, j, a, i, j-1,b);
        return ((M[i - 1][j] < M[i][j - 1]) ? M[i - 1][j] : M[i][j - 1]) + m[i][j];
    }
}
int main(void)
{
    int m[4][4] =  { { 6,7,12,5 },{ 5,3,11,18 },{ 7,17,3,3 },{ 8,10,14,9 } };
    int i, j, r, c;
    //int **M ;
 
    int M[4][4];
    r = c = 4; // 4x4 matrix
 
   
    for(i = 0; i < r; i++)
        for (j = 0; j < c; j++)
        {
            M[i][j] = 0;
 
       
        }
       
 
 
        printf("%d\n", matrixPath(m, r, c, 3, 3, M));
}

 

 

 

저작자 표시 비영리 변경 금지
신고
Posted by 친절한 LEELAB

 순환을 이용한 피보나치 수열

같은 계산을 또 하지 않기 위해 F배열에 값을 메모한다.

 

#include <stdio.h>
#include <stdlib.h>
 
int fib(int n, int* F) {
    if (n == 1 || n == 2)
        return 1;
    if (F[n - 1] == 0)
        F[n - 1] = fib(n - 1, F);
    if (F[n - 2] == 0)
        F[n - 2] = fib(n - 2, F);
    printf("%d ", F[n - 1] + F[n - 2]);
    return F[n - 1] + F[n - 2];
}
 
int main(void)
{
    int n, i;
    int *F;
  
 
    printf("몇 번째까지의 피보나치 수열:");
    scanf("%d", &n); //fn
 
                    
    F = (int*)malloc(sizeof(int)*(n + 1));
                    
    for (i = 0; i < n; i++)
        F[i] = 0;
                 
    fib(n, F);
}
 
저작자 표시 비영리 변경 금지
신고
Posted by 친절한 LEELAB

 순환을 이용한 조합

m 배열에 값을 메모한다.

#include<stdio.h>
int comb(int n, int r, int *m);
int main()
{
    int c;
    int i;
    int n, r;
    int *m;
    printf("enter number n and r (nCr)\n");
    printf("n:");
    scanf("%d", &n);
    printf("r:");
    scanf("%d", &r);
 
    m = (int*)malloc(sizeof(int) * (r + 1));
    for (i = 0; i <= r; i++)
        m[i] = 0;
    c = comb(n, r, m);
    printf("%d", c);
 
    return 0;
}
int comb(int n, int r, int *m)
{
    if (r == n || r == 0)
        return 1;
    if (n - 1 == r)
    {
 
        if(m[r] == 0)
            m[r] = comb(n - 1, r - 1, m) + comb(n - 1, r, m);
        return m[r];
    }
   
    return comb(n - 1, r - 1, m) + comb(n - 1, r, m);
}
 
 
저작자 표시 비영리 변경 금지
신고

'개발 공부 > C' 카테고리의 다른 글

[c언어] 순환 / 큰 값으로 만들어주는 길 찾기  (0) 2017.10.04
memorization / 피보나치 수열  (0) 2017.10.04
memorization / 조합 combination  (0) 2017.10.04
[c언어] 미로 길 찾기  (0) 2017.10.04
[c언어] 디버깅 debuging  (0) 2017.09.28
[c언어] string.h 함수  (0) 2017.09.28
Posted by 친절한 LEELAB

미로 길 찾기

 

 

#include <stdio.h>
#include <stdlib.h>
 
int matrixPath(int **m, int r, int c, int i, int j, int **M, int **N)
{
    if (i == 0 && j == 0)
        return m[i][j];
   
    else if (i == 0)
    {
        if (N[0][j] == 0)
        {
            M[0][j] = matrixPath(m, r, c, 0, j - 1, M, N) + m[i][j];
            N[0][j] = 1;
        }
        return M[0][j];
    }
    else if (j == 0)
    {
        if (N[i][0] == 0)
        {
            M[i][0] = matrixPath(m, r, c, i - 1, 0, M, N) + m[i][j];
            N[i][0] = 1;
 
        }
        return M[i][0];
    }
    else
    {
        int a, b;
        if (N[i - 1][j] == 0)
        {
            M[i - 1][j] = matrixPath(m, r, c, i - 1, j, M, N);
            N[i - 1][j] = 1;
        }
        if (N[i][j - 1] == 0)
        {
            M[i][j - 1] = matrixPath(m, r, c, i, j - 1, M, N);
            N[i][j - 1] = 1;
        }
        a = M[i - 1][j];
        b = M[i][j - 1];
        return ((a < b) ? a : b) + m[i][j];
    }
}
int main(void)
{
 
    int i, j, r, c;
    int **M;
    int **N;
    int **m;
    printf("enter row and column\n");
    printf("number of row:");
    scanf("%d", &r);
    printf("number of column:");
    scanf("%d", &c);
    m = (int**)malloc(sizeof(int*) * r);
    M = (int**)malloc(sizeof(int*) * r);
    N = (int**)malloc(sizeof(int*) * r);
    for (i = 0; i < r; i++)
    {
        m[i] = (int*)malloc(sizeof(int) * c);
        M[i] = (int*)malloc(sizeof(int) * c);
        N[i] = (int*)malloc(sizeof(int) * c);
    }
   
    for (i = 0; i < r; i++)
        for (j = 0; j < c; j++)
        {
            M[i][j] = 0;
            N[i][j] = 0;
        }
    printf("%d x %d 행렬의 값을 입력하세요:\n", r, c);
   
    for (i = 0; i < r; i++)
        for (j = 0; j < c; j++)
            scanf("%d", &m[i][j]);
 
    printf("%d\n", matrixPath(m, r, c, r - 1, c - 1, M, N));
    for (i = 0; i < r; i++)
    {
        free(m[i]);
        free(M[i]);
        free(N[i]);
    }
 
    free(m);
    free(M);
    free(N);
}

 

#include <stdio.h>
#include <stdlib.h>
#include<stdbool.h>
 
int matrixPath(int m[][4], int r, int c, int i, int j, int M[][4], bool check[][4]);
int main(void)
{
   
    int m[4][4] = { { 6,7,12,5 },{ 5,3,11,18 },{ 7,17,3,3 },{ 8,10,14,9 } };
    int i, j, r, c;
    bool check[4][4] = { false };
 
    int M[4][4] = {0};
    r = c = 4;
   
    printf("%d\n", matrixPath(m, r, c, 3, 3, M, check));
}
int matrixPath(int m[][4], int r, int c, int i, int j, int M[][4], bool check[][4])
{
    if (i == 0 && j == 0)
    {
        printf("m[%d][%d] :%d  \n", i, j, m[i][j]);
        return m[i][j];
    }
    else if (i == 0)
    {
        if (!check[0][j])
        {
 
            M[0][j] = matrixPath(m, r, c, 0, j - 1, M, check) + m[i][j];
            check[0][j] = true;
        }
        printf("M[%d][%d] :%d  \n", i, j, M[i][j]);
 
        return M[0][j];
 
    }
    else if (j == 0)
    {
        if (!check[i][0])
        {
 
 
            M[i][0] = matrixPath(m, r, c, i - 1, 0, M, check) + m[i][j];
 
            check[i][0] = true;
        }
        printf("M[%d][%d] :%d  \n", i, j, M[i][j]);
 
        return M[i][0];
 
    }
    else
    {
        int a, b;
        if (!check[i - 1][j])
        {
            M[i - 1][j] = matrixPath(m, r, c, i - 1, j, M, check);
            check[i - 1][j] = true;
        }
        if (!check[i][j - 1])
        {
            M[i][j - 1] = matrixPath(m, r, c, i, j - 1, M, check);
            check[i][j - 1] = true;
        }
    
 
        return ((M[i - 1][j] < M[i][j - 1]) ? M[i - 1][j] : M[i][j - 1]) + m[i][j];
    }
}

 
저작자 표시 비영리 변경 금지
신고

'개발 공부 > C' 카테고리의 다른 글

memorization / 피보나치 수열  (0) 2017.10.04
memorization / 조합 combination  (0) 2017.10.04
[c언어] 미로 길 찾기  (0) 2017.10.04
[c언어] 디버깅 debuging  (0) 2017.09.28
[c언어] string.h 함수  (0) 2017.09.28
[c언어] scanf / gets / fgets  (0) 2017.09.28
Posted by 친절한 LEELAB