发表于 | 阅读次数:

统计每个月兔子的总数

1
2
题目描述
有一只兔子，从出生后第3个月起每个月都生一只兔子，小兔子长到第三个月后每个月又生一只兔子，假如兔子都不死，问每个月的兔子总数为多少？
1
2
3
4
5
6
7
8
9
10
11
输入描述:
输入int型表示month

输出描述:
输出兔子总数int型

示例1
输入
9
输出
34

这道题贼简单,就是一个斐波那契数列递归实现:
F(N)=F(N-1)+F(N-2)
F(1)=1
F(2)=1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def Feibo(N):
    if N==1:
        return 1
    elif N==2:
        return 1
    else:
        return Feibo(N-1)+Feibo(N-2)
    
    
while True:
    try:
        n=int(raw_input())
        r=Feibo(n)
        print r
    except:
        break

放苹果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
题目描述
题目描述

把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。


输入

每个用例包含二个整数M和N。0<=m<=10，1<=n<=10。


样例输入

7 3


样例输出

8

这道题想到递归的确有点绕,一位博主的解题思路:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
放苹果分为两种情况，一种是有盘子为空，一种是每个盘子上都有苹果。
令(m,n)表示将m个苹果放入n个盘子中的摆放方法总数。
1.假设有一个盘子为空，则(m,n)问题转化为将m个苹果放在n-1个盘子上，即求得(m,n-1)即可
2.假设所有盘子都装有苹果，则每个盘子上至少有一个苹果，即最多剩下m-n个苹果，问题转化为将m-n个苹果放到n个盘子上
即求(m-n，n)
递归还需要确定递归基准条件
m=1或n=1时,只有一种摆法
m=0时,苹果不存在,就不存在摆法-->0
综上所述：
(m，n)=(m,n-1)+(m-n,n);
(m,1)=(1,n)=1,m>0,n>0
(0,n)=0
还有边界问题需要考虑
但是这么做还是有个致命的问题!!!
针对第二个条件的时候,m-n等于0的时候,根本不存在递归的问题了,只能放一种,但是(0,n)的递归限制,会在(m，n)=(m,n-1)+(m-n,n);对最后一项变为0!!!!就比原来的少了!!!!
So 现在给出精确的解法:
(0,n)=0
(1,n)=(m,1)=(1,1)=1 m>0,n>0
(m,n)=(m,n-1)+(m-n,n) m-n>0,n>0
(m,n)=(m,n-1)+1 m-n=0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def putApple(M,N):
    if M<=0:
        return 0
    if M==1 or N==1:
        return 1
    if M>0 and M-N==0:
        return putApple(M,N-1)+1

    return putApple(M,N-1)+putApple(M-N,N)


while True:
    try:
        M,N=map(int,raw_input().split())
        r=putApple(M,N)
        print r
    except:
        break

发表于 | 阅读次数:

LIS问题编程问题总结

比较好的讲解博客

问题的描述:

1
一个数的序列bi，当b1 < b2 < … < bS的时候，我们称这个序列是上升的。对于给定的一个序列(a1, a2, …, aN)，我们可以得到一些上升的子序列(ai1, ai2, …, aiK)，这里1 <= i1 < i2 < … < iK <= N。比如，对于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4，比如子序列(1, 3, 5, 8).

最好记忆的方式:贪心算法

记住三个步骤:

1
2
3
状态设计：F[i]代表以A[i]结尾的LIS的长度
状态转移：F[i]=max{F[i],F[j]+1}(1<=j< i,A[j]< A[i])
边界处理：F[i]=1(1<=i<=n)

这个算法的复杂度在O(N^2)
选取每个点出发,长度最起码是1,这个边界没问题,如果加上的项比原来的大,长度就会增大,F[j表示的是A[j]结尾最长的LIS长度,就是递归,不需要先考虑前面F[j]则得到,只关心当前的F[i]要最优,一步步反推回去,就得到了解

阅读全文 »

发表于 | 阅读次数:

题目描述:

1
2
3
4
5
6
7
8
9
10
11
12
13
•计算一个数字的立方根，不使用库函数

详细描述：

•接口说明

原型：

public static double getCubeRoot(double input)

输入:double 待求解参数

返回值:double  输入参数的立方根
1
2
3
4
5
示例1
输入
216
输出
6.0
阅读全文 »

发表于 | 阅读次数:

题目描述

1
2

正整数A和正整数B 的最小公倍数是指 能被A和B整除的最小的正整数值，设计一个算法，求输入A和B的最小公倍数。

输出描述:

1
输入两个正整数A和B。

输出描述:

1
输出A和B的最小公倍数。

实例:

1
2
3
4
5
输入:
5
7
输出:
35

阅读全文 »

发表于 | 阅读次数:

re模块导入的语法小例子:

1
2
3
4
5
6
7
8
9
10
11
import re #导入模块名

p = re.compile("^[0-9]") 
#生成要匹配的正则对象 ， ^代表从开头匹配，[0-9]代表匹配0至9的任意一个数字， 所以这里的意思是对传进来的字符串进行匹配，如果这个字符串的开头第一个字符是数字，就代表匹配上了

m = p.match(‘14534Abc‘)   #按上面生成的正则对象 去匹配 字符串， 如果能匹配成功，这个m就会有值， 否则m为None

if m: #不为空代表匹配上了
　　print(m.group())　　　　#m.group()返回匹配上的结果，此处为1，因为匹配上的是1这个字符
else:
　　print("doesn‘t match.")

上述的re.compile和re.match可以进行合并简写

1
m=p.match("^[0-9]","14534Abc")

效果是一样的，区别在于，第一种方式是提前对要匹配的格式进行了编译（对匹配公式进行解析），这样再去匹配的时候就不用在编译匹配的格式，第2种简写是每次匹配的时候 都 要进行一次匹配公式的编译，第一种匹配在文本量大的时候,匹配速度更快

阅读全文 »

发表于 | 阅读次数:

C++的常考面试题:

以下资料整理转自牛客网
牛客网习题链接

试题1

下面代码会出现什么问题？

1
2
3
4
5
6
7
8
9
10
11
char *GetMemory( void )
{ 
 char p[] = "hello world"; 
 return p; 
}
void Test( void )
{ 
 char *str = NULL; 
 str = GetMemory(); 
 printf( str ); 
}

阅读全文 »

发表于 | 阅读次数:

廖雪峰老师的课件中的内容

课件视频
python引入模块的概念就是将代码拆分,易于维护,同一个名字的变量在不同的文件中(模块中)互不以影响:
比如图中所示:

引用其他模块的实例:

1
import 模块名

阅读全文 »

发表于 | 阅读次数:

#python进阶学习笔记1(廖雪峰课程)

##高阶函数
python和Js很像,支持将函数作为变量输入到参数的参数里面去,此时将函数作为参数的函数称之为高阶函数
变量也是可以指向函数的,例如:

1
2
3
fun=abs()
fun(-10) 
#输出的结果就是 abs(-10)=10的结果

一般存在一下几个常用的高阶函数,将list和function作为参数输入处理:

阅读全文 »