文档章节

UVA 104 - Arbitrage

aqia358
 aqia358
发布于 2014/06/04 15:24
字数 500
阅读 56
收藏 0

这道题的题意是:给出n种国家的货币汇率,一定金额的某种货币经过一系列汇率变换后再换成原来货币,金额增加了,求出这样的一个变换,要求变换步数最少。

由于数据量不大,我们可以直接用动规+floyd解决,设f[p][i][j]为由i到j经过p次转换所能达到的最大汇率乘积,每循环一次p我们就扫描一遍f[p][i][i],如果有大于1的情况就直接打印结果即可。

    在记录路径时用path[p][i][j]记录第k次转换的初始位置,打印时采用递归的方式。

Sample Input

3

1.2 .89
.88 5.1
1.1 0.15
4
3.1    0.0023    0.35
0.21   0.00353   8.13 
200    180.559   10.339
2.11   0.089     0.06111
2
2.0
0.45

Sample Output

1 2 1

1 2 4 1
no arbitrage sequence exists

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;

public class Arbitrage {

	public static int n;
	public static float[][][] f;
	public static int[][][] path;

	public static void floyd() {
		int p, i, j, k;
		p = i = j = k = 0;
		for (p = 1; p < n; p++) {
			for (i = 0; i < n; ++i)
				for (j = 0; j < n; ++j)
					for (k = 0; k < n; ++k) {//找到f(p-1)到f(p)转换的最大值保存下来,同时保存转换路径
						if (f[p - 1][i][k] * f[0][k][j] > f[p][i][j]) {
							f[p][i][j] = f[p - 1][i][k] * f[0][k][j];
							path[p][i][j] = k;
						}
					}
			for (int m = 0; m < n; ++m) {
				if (f[p][m][m] > 1) {
					// System.out.println("find some thing");
					print(m, m, p);
					System.out.println();
				}
			}
		}
	}

	public static void print(int i, int j, int p) {
		if (p == 0) {
			System.out.print(i+" ");//打印起点
			System.out.print(j+" ");//打印起点后打印途径点
		} else {
			print(i, path[p][i][j], p - 1);//先遍历到起点再开始打印
			System.out.print(j+" ");//打印途径点
		}
	}

	public static void main(String[] args) {
		try {
			FileInputStream fis = new FileInputStream(new File("D:/a.txt"));
			StreamTokenizer st = new StreamTokenizer(new BufferedReader(
					new InputStreamReader(fis)));
			while (st.nextToken() != StreamTokenizer.TT_EOF) {
				System.out.println("-------");
				n = (int) st.nval;
				f = new float[n][n][n];
				path = new int[n][n][n];
				for (int i = 0; i < n; ++i) {
					for (int j = 0; j < n; ++j) {
						if (i == j)
							f[0][i][j] = 1;
						else {
							st.nextToken();
							f[0][i][j] = (float) st.nval;
						}
					}
				}
				floyd();
			}
		} catch (Exception e) {
			e.printStackTrace();
		}
	}

}




© 著作权归作者所有

共有 人打赏支持
aqia358
粉丝 6
博文 82
码字总数 30297
作品 0
海淀
程序员
POJ 2240-Arbitrage(SPFA判断正环-邻接矩阵+邻接表)

Description Arbitrage is the use of discrepancies in currency exchange rates to transform one unit of a currency into more than one unit of the same currency. For example, suppo......

Akatsuki__Itachi
01/20
0
0
[笔记]Implied Risk Neutral Distribution

1. 前言 最近关注了一个非常不错的微信公众号,叫做伽玛交易员(微信号:gammatrader)。微信号的主人是一位非常出色的期权交易员,之前一直在香港从事期权交易。网上有一篇关于他的小传htt...

Clever Liu
2016/07/19
0
0
robocup uva老版本代码改写

老代码Uva或者二进制不能连接,解决问题看这里:http://sourceforge.net/forum/forum.php?threadid=2055268&forumid=76439 针对这个问题的解答,我摘录到这里 Almost all past binaries and...

枫言风语
2012/09/01
0
0
Python 数据驱动编程框架 - Databot

用于 Web 爬虫、ETL、数据管道任务开发的高性能 Python 数据驱动编程框架。 特性: 数据驱动编程框架 基于协程的并行 基于类型和内容的函数路由 安装: pip install -U databot Databot is....

匿名
08/28
0
0
vn.py 1.9.0 发布,开源量化交易程序开发框架

vn.py 是基于 Python 的开源量化交易程序开发框架,起源于国内私募的自主量化交易系统,目前已经成长为一套全功能的交易程序开发框架。 vn.py 1.9.0 更新内容: 底层接口: 新增和优化一系列...

王练
08/14
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Asus RamPage VI Extreme开不了机

Asus RamPage VI Extreme 的机器突然关机,然后就再也开不了机,没有任何反应。有人说是BIOS问题,可是这个连Bios都进不去的,按后面的刷新Bios、清除CMOS等都没有什么效果,没有任何反应。 ...

openthings
31分钟前
1
0
ubuntu 18.04 desktop 截图快捷键

如图,点击下方的 add shortcut 为这个快捷键命名 输入截图 command gnome-screenshot -a 设置快捷键 常用为 Ctrl - Alt + a 参考 http://os.51cto.com/art/200903/113091_all.htm...

公孙衍
40分钟前
0
0
一个六年Java程序员的从业总结:比起掉发,我更怕掉队

恍然间,发现自己在这个行业里已经摸爬滚打了五、六年了,原以为自己就凭已有的项目经验和工作经历怎么着也应该算得上是一个业内比较资历的人士了,但是今年在换工作的过程中却遭到了重大的挫...

老道士
43分钟前
18
2
Spacemacs快捷键

由于Spacemacs快捷键太多,为方便使用,将常用的快捷键记录在此。 以下快捷键都是在emacs的evil模式下 Buffers操作 创建名称为<buffer-name>的buffer SPC b b <buffer-name> 从已打开的buf...

yxmsw2007
47分钟前
1
0
GO冒泡,二分查找

package mainimport("fmt")func main() {var arr [5]int = [5]int{11,13,9,2,25}maopao(&arr)fmt.Println("arr = ", arr) //[2 9 11 13 25]findIndex := binaryFind(&arr, 0......

汤汤圆圆
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部