Hibernate animals proliferation

351 0 0

作者:shepherd_gai

Problem:

　　There is a kind of unicellular organism, it starts to generate one offspring per day on the 5th day after birth, and it starts to hiberate on the 9th day after birth. Now suppose the starting date is day 1 and there is one such new born animal, what is the number of the animals on the nth day?

We should maintain a data structure to count the number of animals based on their ages and set up the state transfer function:

　　Define function counter(a, d) to denote the number of animals that are on their ath day after birth on day d. Since animals are inactive from the 9th day after birth, all animals that are 9 or more days old are marked 9 days old.

　　At the beginning,

　　counter(1, 1)=1

　　counter(2, 1)=0

　　counter(3, 1)=0

　　counter(4, 1)=0

　　counter(5, 1)=0

　　counter(6, 1)=0

　　counter(7, 1)=0

　　counter(8, 1)=0

　　counter(9, 1)=0

　　At day d the following equations hold:

　　counter(1, d)=counter(4, d-1)+counter(5, d-1)+counter(6, d-1)+counter(7, d-1)

　　counter(2, d)=counter(1, d-1)

　　counter(3, d)=counter(2, d-1)

　　counter(4, d)=counter(3, d-1)

　　counter(5, d)=counter(4, d-1)

　　counter(6, d)=counter(5, d-1)

　　counter(7, d)=counter(6, d-1)

　　counter(8, d)=counter(7, d-1)

　　counter(9, d)=counter(8, d-1)+counter(9, d-1)

Then we can accumulate number of animals and get the final result.

Code:

public static int proliferation(int day) {
    int[] prev= {1,0,0,0,0,0,0,0,0};
    int[] cur=new int[9];
    
    int i=1;
    while(i<day) {
        for(int j=0;j<9;j++) {
            switch(j) {
                case 0:{
                    cur[j]=prev[3]+prev[4]+prev[5]+prev[6];
                } break;
                case 8:{
                    cur[j]=prev[7]+prev[8];
                } break;
                default:{
                    cur[j]=prev[j-1];
                } break;
            }
        }
        prev=cur;
        cur=new int[9];
        i++;
    }
    
    int res=0;
    for(int j=0;j<9;j++)
        res+=prev[j];
    return res;
}

Note there exists a O(log n) algorithm which applies matrix multiplication.

内容来源于网络如有侵权请私信删除

文章来源: 博客园

原文链接: https://www.cnblogs.com/shepherdgai/p/13616507.html

标签：算法数据结构

你还没有登录，请先登录或注册！

还没有人评论，欢迎说说您的想法！

Hibernate animals proliferation