TZOJ 1376 母牛的故事(递推和递归)

2023-11-30 16:04

本文主要是介绍TZOJ 1376 母牛的故事(递推和递归),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

答案1(递推):


#include<stdio.h>
int main() 
{int n=0,i=0;int a[55] = { 0,1,2,3,4 };   //数组下标就相当于过了几年,以第四年母牛生出的第一只小母牛成年为周期,初始化前四年的值while (scanf("%d", &n) == 1 && (n >= 0 && n < 55))   //使输入符合if (n == 0)   //如果输入0break;     //跳出循环else    //如果输入不是0{if (n <= 4)   //如果在四年内,就没必要递推printf("%d\n", a[n]);   //直接打印母牛个数else     //如果超过四年,就要用递推了{for (i = 5; i <= n; i++)   //从最小递推年数第5年开始,循环至n年(要用<=,不然第5年就直接没算了){a[i] = a[i - 1] + a[i - 3];    //母牛递推规律(推导解释在文末)if (i == n)    //如果到了输入的n年{a[n] = a[i];   //将此时的个数赋值给输出printf("%d\n", a[n]);   //打印第n年母牛的个数}}}} return 0;
}

答案2(递归):

# include<stdio.h>
int fun(int n)   //定义母牛个数的函数
{if (n == 1)    //第一年的个数return 1;else if (n == 2)   //第二年的个数return 2;else if (n == 3)    //第三年的个数return 3;else if (n == 4)    //第四年的个数return 4;else     //超出四年{return fun(n - 1) + fun(n - 3);   //用递归母牛的规律公式(推导解释在文末)}
}
int main()
{int n=0;while (scanf("%d", &n) == 1 && (n >= 0 && n < 55))   //使输入符合题目要求if (n == 0)   //如果n=0{break;   //跳出循环}else   //如果n不为0printf("%d\n", fun(n));   //调用上面函数,然后打印return 0;
}

关于本题的知识点以及需要理解的点:

1.第一年母牛是不生的!!!也就是说从第二年母牛才开始生,这是要理解题目的点(大概是题目里每年年初是暗示吧)

2.

母牛个数规律推导:

首先:今年母牛的个数等于去年母牛的个数+今年新生的小母牛个数,然后去年母牛的个数等于去年的去年母牛的个数+去年新生的小母牛个数……直到第四年只有初始母牛在生小母牛

所以

f[i]=今年母牛的个数
f[i-1]=去年母牛的个数
f[i-3]=3年前母牛的个数=今年成年的母牛的个数(因为3年前加上本年等于4年)=今年能够生小母牛的母牛个数(即满4年的成年母牛的个数)=今年新生的小母牛个数
f[i]今年母牛的个数=f[i-1]去年母牛的个数+f[i-3]今年新生的小母牛个数 
故f[i] = f[i - 1] + f[i - 3] 

3.递推和递归的区别

递推:本题求第n年的牛总数,已知第一年为“1”头,进而推出第二年“2”头,第三年“3”头,“4”头,“6”头,“9”头……

递归:要想求第“n”年的牛的总数,只要知道“n-1”和“n-3”年的牛的总数,再依次向前推
所以递推和递归是一个正向思维一个逆向思维

4.在TZOJ上本题只能用递推,递归会超时

这篇关于TZOJ 1376 母牛的故事(递推和递归)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/437662

相关文章

uva 568 Just the Facts(n!打表递推)

题意是求n!的末尾第一个不为0的数字。 不用大数,特别的处理。 代码: #include <stdio.h>const int maxn = 10000 + 1;int f[maxn];int main(){#ifdef LOCALfreopen("in.txt", "r", stdin);#endif // LOCALf[0] = 1;for (int i = 1; i <=

PHP实现二叉树遍历(非递归方式,栈模拟实现)

二叉树定义是这样的:一棵非空的二叉树由根结点及左、右子树这三个基本部分组成,根据节点的访问位置不同有三种遍历方式: ① NLR:前序遍历(PreorderTraversal亦称(先序遍历)) ——访问结点的操作发生在遍历其左右子树之前。 ② LNR:中序遍历(InorderTraversal) ——访问结点的操作发生在遍历其左右子树之中(间)。 ③ LRN:后序遍历(PostorderT

oracle11.2g递归查询(树形结构查询)

转自: 一 二 简单语法介绍 一、树型表结构:节点ID 上级ID 节点名称二、公式: select 节点ID,节点名称,levelfrom 表connect by prior 节点ID=上级节点IDstart with 上级节点ID=节点值 oracle官网解说 开发人员:SQL 递归: 在 Oracle Database 11g 第 2 版中查询层次结构数据的快速

Leetcode面试经典150题-128.最长连续序列-递归版本另解

之前写过一篇这个题的,但是可能代码比较复杂,这回来个简洁版的,这个是递归版本 可以看看之前的版本,两个版本面试用哪个都保过 解法都在代码里,不懂就留言或者私信 class Solution {/**对于之前的解法,我现在提供一共更优的解,但是这种可能会比较难懂一些(思想方面)代码其实是很简洁的,总体思想如下:不需要排序直接把所有数放入map,map的key是当前数字,value是当前数开始的

【UVA】10651-Pebble Solitaire(直接递归或者记忆化)

不知道这个题UVA的数据是怎么的,用2个方法交了,第一次直接递归,第二次记忆化剪枝,时间竟然一样!? 直接郁闷了,简单的二进制表示状态和二进制运算。 14145176 10651 Pebble Solitaire Accepted C++ 0.009 2014-09-04 09:18:21 #include<cstdio>#include<algorithm>#inclu

笔试强训,[NOIP2002普及组]过河卒牛客.游游的水果大礼包牛客.买卖股票的最好时机(二)二叉树非递归前序遍历

目录 [NOIP2002普及组]过河卒 牛客.游游的水果大礼包 牛客.买卖股票的最好时机(二) 二叉树非递归前序遍历 [NOIP2002普及组]过河卒 题里面给的提示很有用,那个马的关系,后面就注意,dp需要作为long的类型。 import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息publ

HCIA--实验十:路由的递归特性

递归路由的理解 一、实验内容 1.需求/要求: 使用4台路由器,在AR1和AR4上分别配置一个LOOPBACK接口,根据路由的递归特性,写一系列的静态路由实现让1.1.1.1和4.4.4.4的双向通信。 二、实验过程 1.拓扑图: 2.步骤: (下列命令行可以直接复制在ensp) 1.如拓扑图所示,配置各路由器的基本信息: 各接口的ip地址及子网掩码,给AR1和AR4分别配置

HLJUOJ1128 HDU2046(数学递推)

1128: 递推求解专题练习三 Time Limit: 1 Sec   Memory Limit: 128 MB Submit: 8   Solved: 6 [ Submit][ Status][ Web Board] Description 在2×n的一个长方形方格中,用一个1× 2的骨牌铺满方格,输入n ,输出铺放方案的总数。 例如n=3时,为2× 3方格,骨牌的铺放方案有三

Winform中在窗体中的Paint事件中重绘会导致递归问题?

在 WinForms 应用程序中,如果在窗体的 Paint 事件处理程序中不断调用 Invalidate 方法,确实可能会导致递归调用的问题。这是因为每次调用 Invalidate 方法时,都会向消息队列添加一个绘制消息,当消息队列中的绘制消息被处理时,会触发 Paint 事件。如果 Paint 事件处理程序中又调用了 Invalidate,就会形成一个循环,导致递归调用 Paint 事件,这

每日OJ_牛客_求和(递归深搜)

目录 牛客_求和(递归深搜) 解析代码 牛客_求和(递归深搜) 求和_好未来笔试题_牛客网 解析代码         递归中每次累加一个新的数,如果累加和大于等于目标,结束递归。此时如果累加和正好等于目标,则打印组合。向上回退搜索其它组合。此题本身就是一个搜索的过程,找到所有的组合。 #include <iostream>#include <cmath>#in