矩阵链乘
2021/12/6 23:22:34
本文主要是介绍矩阵链乘,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
#include <iostream> #include<bits/stdc++.h> #include <algorithm> #include <chrono> using namespace std; ofstream file_out, time_out; const int maxn = 100 + 50; double time_list[5]; void print(int s[][150], int i, int j){ if(i == j) file_out << "A" << i; else{ file_out << "("; print(s, i, s[i][j]); print(s, s[i][j] + 1, j); file_out << ")"; } } int main(){ string from = "C:\\Users\\ASUS\\Desktop\\AL\\ex1\\input\\1_1_input.txt"; string dest = "C:\\Users\\ASUS\\Desktop\\AL\\ex1\\output\\result.txt"; string time = "C:\\Users\\ASUS\\Desktop\\AL\\ex1\\output\\time.txt"; ifstream file_in; file_in.open(from); file_out.open(dest); time_out.open(time); for(int i = 0; i < 5; i++){ long long nums[maxn]; long long dp[maxn][maxn]; int s[maxn][maxn]; int N; file_in >> N; for (int i = 0; i <= N; i++) file_in >> nums[i]; chrono::steady_clock::time_point t1 = chrono::steady_clock::now(); for(int i = 1; i<= N; i++) dp[i][i] = 0; for (int len = 2; len <= N; len++) { for (int i = 1; i <= N - len + 1; i++) { int j = i + len - 1; dp[i][j] = 9223372036854775807; for (int k = i; k < j; k++) { long long tmp = dp[i][k] + dp[k + 1][j] + nums[i-1] * nums[k] * nums[j]; if(tmp < dp[i][j]){ dp[i][j] = tmp; s[i][j] = k; } } } } chrono::steady_clock::time_point t2 = chrono::steady_clock::now(); file_out << dp[1][N] << endl; print(s, 1, N); file_out << endl; chrono::duration<double> time_span = chrono::duration_cast<chrono::duration<double>>(t2 - t1); time_list[i] = time_span.count(); if(i == 0){ for(int j = 1; j<= N; j++){ for(int l = j; l <= N; l++) cout << "m[" << j << "][" << l << "]=" << dp[j][l] << " "; cout << endl; } for(int j = 1; j<= N-1; j++){ for(int l = j+1; l <= N; l++) cout << "s[" << j << "][" << l << "]=" << s[j][l] << " "; cout << endl; } } } for(int i = 0; i < 5; i++){ time_out << time_list[i] << "s" << endl; } return 0; }
这篇关于矩阵链乘的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-19永别了,微服务架构!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?