小羊能活5歲,它在2歲,4歲的時(shí)候都會(huì)生一只小羊,5歲的時(shí)候就死亡了。
問(wèn):現(xiàn)在有一只剛出生的小羊(0歲),n年后有多少只羊?
一個(gè)遞推就可以了,php我不熟,Ruby的代碼如下:
// 初始化0歲的羊有1只,其它歲的羊有0只
y0 = [1]
y1 = [0]
y2 = [0]
y3 = [0]
y4 = [0]
y5 = [0]
# 暫定n = 20年
n = 20
(1..n).each do |i|
// 2歲羊和5歲羊產(chǎn)仔tmp只
tmp = y2[i-1].to_i + y5[i-1].to_i
// 羊依次漲1歲
y5[i] = y4[i-1].to_i
y4[i] = y3[i-1].to_i
y3[i] = y2[i-1].to_i
y2[i] = y1[i-1].to_i
y1[i] = y0[i-1].to_i
// 0歲羊
y0[i] = tmp
end
p y0[n] + y1[n] + y2[n] + y3[n] + y4[n] + y5[n]
如果羊M歲才死,那么就需要開(kāi)個(gè)數(shù)組,做兩層循環(huán)來(lái)地推。
數(shù)學(xué)思維
//年數(shù)
$n = 30;
//已知1,第2年2只,第4年4只, 第6年開(kāi)始死亡。。 從第6年開(kāi)始用程序計(jì)算
$count = [4, 2, 1];
for ($i = 6; $i <= $n; $i += 2) {
//上一季羊的數(shù)量除2得到媽媽數(shù),上上季羊除2得到上上季媽媽數(shù),兩者之差為上一紀(jì)要淘汰的數(shù)量,剩下的乘2便得出本季媽媽和女兒的總數(shù)
array_unshift($count,($count[0] - ($count[0] / 2 - $count[1] / 2)) * 2);
}
//每?jī)赡隇橐患?,每季羊?shù)量
sort($count);
var_dump($count);
0 => int 1
1 => int 2
2 => int 4
3 => int 6
4 => int 10
5 => int 16
6 => int 26
7 => int 42
8 => int 68
9 => int 110
10 => int 178
11 => int 288
12 => int 466
13 => int 754
14 => int 1220
15 => int 1974
第一種:
function born($n){
$all=[0];
for($i=0;$i<$n;$i++){
$c=count($all);
for($j=0;$j<$c;$j++){
$all[$j]=$age=$all[$j]+1;
if($age==2||$age==4){
$all[]=0;
}
}
}
return $all;
}
//返回的數(shù)據(jù)中,把大于等于5的去掉就是了。
第二種:(在 @雪之祈舞 的回答上作了一點(diǎn)修改)
function sheep($n){
$y=[
0=>1,
1=>0,
2=>0,
3=>0,
4=>0,
5=>0,
];
for($i=0;$i<$n;$i++){
for($j=5;$j>0;$j--){
$y[$j]=$y[$j-1];
}
$born=$y[2]+$y[4];
$y[0]=$born;
}
return $y;
}
//unset($y[5]) 再把各項(xiàng)加起來(lái)就可以了。
兩種方法得到的結(jié)果是一樣的,但第一種方法不斷往數(shù)組里添加剛出生的羊,數(shù)組長(zhǎng)度越來(lái)越大,我測(cè)試了一下,大于 50 的時(shí)候就會(huì)出現(xiàn)內(nèi)存不足的情況了。
而第二種方法則完全不必?fù)?dān)憂。
記錄每一只羊的狀態(tài)
function sheep($n){
$sheep[0]=0;
$count[0]=1;
for($i=1; $i<$n; $i++){
$count=0;
for($j=0; $j<$count[i]; $j++){
if($sheep[i]!=-1){
$sheep[i]++;
if($sheep[i]==2 || $sheep[i]==2 ) $sheep.append(0);
if($sheep[i]>=5) $sheep[i]=-1;
$count++;
}
}
$count[i+1]=$count;
}
return $count[$n];
}
記錄各個(gè)年齡的羊數(shù)
function sheep($n){
$y=[0=>1,1=>0,2=>0,3=>0,4=>0,5=>0];
for($i=1; $i<$n; $i++){
for($j=5;$j>0; $j--){
$y[$j]=$y[$j-1];
}
$new=$y[2]+$[4];
}
return $y;
}
題主希望優(yōu)雅寫法,所以代碼如下:
/**
* [countSheep 數(shù)羊]
* @param $n [年份]
* @return [羊的數(shù)量]
*/
function countSheep($n)
{
static $count = 0; // 初始化羊的數(shù)量
for ($i=0;$i<=5 && $i<=$n;$i++) { // 保證一只羊的壽命小于等于5,不足5時(shí)小于等于$n
if ($i==0)
$count++;
elseif ($i==2 || $i==4)
countSheep($n-$i); // 遞歸調(diào)用,傳入新的年份
elseif ($i==5)
$count--;
}
return $count;
}
<?php
class increase {
// 小羊從0歲開(kāi)始,那么2歲就是第3年,4歲是第5年,死亡是在第6年
function __construct() {
$this->terminal = 6;
$this->give_birth = array(2,4);
$this->sheeps = array(0);
}
function run($year) {
for ($i = 1; $i <= $year; $i++) {
foreach ($this->sheeps as $key=>$age) {
if (in_array($age, $this->give_birth)) {
$this->multiply($key);
}
if ($age == $this->terminal) {
$this->die($key);
}
$this->sheeps[$key] += 1;
}
}
return $this->sheeps;
}
function multiply($key) {
$this->sheeps[] = 0; //繁殖了一只羊
}
function die($sheep) {
unset($this->sheeps[$sheep]); //一只羊的死亡
}
}
$survival = new increase();
$exists = $survival->run(7);
echo count($exists);
function sheep($n, $sum = 1)
{
$arr = [
0 => 0,
1 => 0,
2 => 1,
3 => 0,
4 => 1,
5 => 0,
];
for ($i = 1; $i <= $n; $i++) {
$currentIndex = $i % 6; // 取余數(shù)
if ($arr[$currentIndex] == 1) {
$sum++;
$sum = sheep($n - $i, $sum);
} elseif ($currentIndex == 5) {
$sum--;
}
}
return $sum;
}
$plus = [2,4];//新羊出生
$die = 5;//舊羊死亡
$n = 50;
$sheeps = [];
$sheeps[1] = 0;
for($i = 1; $i <= $n; $i++)
{
foreach($sheeps as $index => $value)
{
$sheeps[$index]++;
if($sheeps[$index] == $die)
{
unset($sheeps[$index]);
continue;
}
if(in_array($sheeps[$index],$plus))
{
$sheeps[] = 0;
}
}
}
echo(count($sheeps));//n=50,242786
北大青鳥(niǎo)APTECH成立于1999年。依托北京大學(xué)優(yōu)質(zhì)雄厚的教育資源和背景,秉承“教育改變生活”的發(fā)展理念,致力于培養(yǎng)中國(guó)IT技能型緊缺人才,是大數(shù)據(jù)專業(yè)的國(guó)家
北大青鳥(niǎo)中博軟件學(xué)院創(chuàng)立于2003年,作為華東區(qū)著名互聯(lián)網(wǎng)學(xué)院和江蘇省首批服務(wù)外包人才培訓(xùn)基地,中博成功培育了近30000名軟件工程師走向高薪崗位,合作企業(yè)超4
中公教育集團(tuán)創(chuàng)建于1999年,經(jīng)過(guò)二十年潛心發(fā)展,已由一家北大畢業(yè)生自主創(chuàng)業(yè)的信息技術(shù)與教育服務(wù)機(jī)構(gòu),發(fā)展為教育服務(wù)業(yè)的綜合性企業(yè)集團(tuán),成為集合面授教學(xué)培訓(xùn)、網(wǎng)
達(dá)內(nèi)教育集團(tuán)成立于2002年,是一家由留學(xué)海歸創(chuàng)辦的高端職業(yè)教育培訓(xùn)機(jī)構(gòu),是中國(guó)一站式人才培養(yǎng)平臺(tái)、一站式人才輸送平臺(tái)。2014年4月3日在美國(guó)成功上市,融資1
曾工作于聯(lián)想擔(dān)任系統(tǒng)開(kāi)發(fā)工程師,曾在博彥科技股份有限公司擔(dān)任項(xiàng)目經(jīng)理從事移動(dòng)互聯(lián)網(wǎng)管理及研發(fā)工作,曾創(chuàng)辦藍(lán)懿科技有限責(zé)任公司從事總經(jīng)理職務(wù)負(fù)責(zé)iOS教學(xué)及管理工作。
浪潮集團(tuán)項(xiàng)目經(jīng)理。精通Java與.NET 技術(shù), 熟練的跨平臺(tái)面向?qū)ο箝_(kāi)發(fā)經(jīng)驗(yàn),技術(shù)功底深厚。 授課風(fēng)格 授課風(fēng)格清新自然、條理清晰、主次分明、重點(diǎn)難點(diǎn)突出、引人入勝。
精通HTML5和CSS3;Javascript及主流js庫(kù),具有快速界面開(kāi)發(fā)的能力,對(duì)瀏覽器兼容性、前端性能優(yōu)化等有深入理解。精通網(wǎng)頁(yè)制作和網(wǎng)頁(yè)游戲開(kāi)發(fā)。
具有10 年的Java 企業(yè)應(yīng)用開(kāi)發(fā)經(jīng)驗(yàn)。曾經(jīng)歷任德國(guó)Software AG 技術(shù)顧問(wèn),美國(guó)Dachieve 系統(tǒng)架構(gòu)師,美國(guó)AngelEngineers Inc. 系統(tǒng)架構(gòu)師。