加载中…
加载中…
标签：
交点线段一元二次方程圆上端点it |
分类： Algorithm |
http://www.thecodeway.com/blog/wp-content/uploads/2011/04/csi.gif
http://www.thecodeway.com/blog/wp-content/uploads/2011/04/csi_2.gif
http://www.thecodeway.com/blog/wp-content/uploads/2011/04/csi_3.gif
http://www.thecodeway.com/blog/wp-content/uploads/2011/04/csi_4.g
标签：
斐波那契非负整数数列程序代码分治法it |
分类： Algorithm |
| 描述 | |
|
斐波那契数列是指如下数列: F(0)=0, F(1)=1,
F(n)=F(n-1)+F(n-2).数列的前10个数如下: |
|
| 关于输入 | |
|
输入包括多组数据. |
|
| 关于输出 | |
| 对于每组数据,你的程序应该输出F(n)对10000取模的结果. |
解题思路：
分析斐波那契数列，我们容易得出这样一个结论：
2 x 2的矩阵{F(n+1), F(n) ; F(n), F(n-1)} = {F(n), F(n-1) ; F(n-1), F(n-2)} *{1, 1 ; 1, 0}
而{F(2), F(1) ; F(1), F(0)} = {1, 1 ; 1, 0}，所以可以得出{F(n+1), F(n) ; F(n), F(n-1)
标签：
马来齐王田忌赛马贪心算法it |
分类： Algorithm |
题目描述：
你一定听过田忌赛马的故事吧？
如果3匹马变成1000匹，齐王仍然让他的马按从优到劣的顺序出赛，田忌可以按任意顺序选择他的赛马出赛。赢一局，田忌可以得到200两银子，输一局，田忌就要输掉200两银子，平局的话不输不赢。
请问田忌最多能赢多少银子?
关于输入
输入包含多组测试数据.
每组测试数据的第一行是一个整数n(1<=n<=1000),表示田忌和齐王都拥有n匹马。接下来一行是n个整数，表示田忌的马的速度，下一行也是n个整数，表示齐王的马的速度。
输入的最后以一个0表示结束。
关于输出
对每组数据，输出一个整数，表示田忌至多可以赢多少银子，如果田忌赢不了，就输出一个负数，表示田忌最少要输多少银子。
解题思路：
算法可以用DP，或者给每匹马连线赋权变为二分图最佳匹配，还有就是贪心了。
1.当田忌最慢的马比齐王最慢的马快，赢一场先
2.当田忌最慢的马比齐王最慢的马慢，和齐王最快的马比，输一场
3.当田忌最快的马比齐王最快的马快时，赢一场先。
4.当田忌最快的马比齐王最快的马慢时，拿最慢的马
