测试input.txt output.txt
/**
*
* 数字三角形问题 -- 动态规划
* ★问题描述：给字一个由n行数字组成的数字三角形（等腰三角形）。试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大。
★算法设计：对于给定的由n行数字组成的数字三角形，计算从三角形的项至底的路径经过的数字和的最大值。
★数据输入：由文件input.txt提供输入数据。文件的第1行是数字三角形的计数n，1≤n≤100。接下来n行是数字三角形各行中的数字。所有数字在0~99之间。
★结果输出：将计算结果输出到文件output.txt。文件第1行中的数是计算出的最大值。
输入文件示例：input.txt
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
输出文件示例：output.txt
30
————————————————
版权声明：本文为CSDN博主「Alexwym」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/Alexwym/article/details/80798493
#include<fstream>
#include<sstream>
ifstream cinfile;
cinfile.open("input.txt",ios::in);
int n;
cinfile>>n;
cinfile.close();
ofstream outfile;
outfile.open("output.txt",ios::out);
outfile<<Max<<endl;
函数传递参数时候：参数：ofstream &outfile
*/
#include<iostream>
#include<stack>
#include<fstream>
#include<sstream>
using namespace std;
//计算数字三角形最大路径的值
int Numtri(int n,int **a,int **r){
r[1][1]=a[1][1];
for(int i=2;i<=n;i++){
int count=1;
for(int j=1;j<=i-1;j++){
r[i][count++]=r[i-1][j]+a[i][j];
r[i][count++]=r[i-1][j]+a[i][j+1];
}
}
}
//回溯最优路径
int Traceback(int n,int posi,int **r,ofstream &outfile){
stack<int>trace; //建立一个堆栈，利用其后进先出的特点来打印出路径
int j=posi/2+1,c=r[n][posi];
for(int i=n-1;i>=0;i--){//从最后一层开始往上回溯
trace.push(c-r[i][j]);
c=r[i][j];
if(j%2==0) j=j/2;
else j=j/2+1;
}
while(!trace.empty()){
outfile<<trace.top()<<" ";
trace.pop();
}
}
int main(){
ifstream cinfile;
cinfile.open("input.txt",ios::in);
int n;
cinfile>>n;
int **NT=new int *[n+1]();
int **ST=new int *[n+1]();
for(int i=0;i<=n;i++)
{
NT[i]=new int[n+1];
ST[i]=new int[2*(n+1)];
}
for(int i=0;i<=n;i++){
NT[0][i]=0;
NT[i][0]=0;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
cinfile>>NT[i][j];
}
for(int j=i+1;j<=n;j++){
NT[i][j]=0;
}
}
for(int i=0;i<=n;i++)
for(int j=0;j<=2*n;j++) ST[i][j]=0;
cinfile.close();
ofstream outfile;
outfile.open("output.txt",ios::out);
Numtri(n,NT,ST);
int Max=ST[n][1],pos=1;
for(int i=2;i<=2*n;i++){
if(Max<ST[n][i]){
Max=ST[n][i];
pos=i;
}
}
outfile<<Max<<endl;
Traceback(n,pos,ST,outfile);
return 0;
}
/*
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
*/ 没有生成也没有写入output.txt todo
/**
*
*
*
* 输入文件示例 输出文件示例
input.txt output.txt
7 7 4
1 2 3 4 5 6 6
本题目不含有价格，是王道上面的汽车加油版本的简化版本
先检测各加油站之间的距离，若发现其中有一个距离大于汽车加满油能跑的距离，则输出no solution
否则，对加油站间的距离进行逐个扫描，尽量选择往远处走，不能走了就让num++，最终统计出来的num便是最少的加油站数
*/
#include <stdio.h>
void greedy(int d[],int n,int k){
FILE *fp;
int num = 0;
for(int i = 0;i <= k;i++){
if(d[i] > n){
printf("no solution!其中有一个距离大于汽车加满油能跑的距离！\n");
return;
}
}
for(int i=0,s=0;i<=k;i++){
s += d[i];
if(s > n) {
num++;
s = d[i];
}
}
printf("最少加油次数为：%d\n",num);
fp=fopen("output.txt","w");
fprintf(fp,"%d",num);
}
int main(){
int i,n,k;
int d[1000];
FILE *fp;
fp=fopen("input.txt","r");
fscanf(fp,"%d%d",&n,&k);
printf("汽车加满油后可行驶: %d km\n旅途中加油站个数为: %d \n",n,k);
for(i=0;i<=k;i++)
fscanf(fp,"%d",&d[i]);
greedy(d,n,k);
fclose(fp);
return 0;
} 修改为以下形式 输入输出成功
#include <iostream> #include <fstream> #include <sstream> using namespace std; void greedy(int d[],int n,int k){ // FILE *fp; ofstream outfile; int num = 0; for(int i = 0;i <= k;i++){ if(d[i] > n){ printf("no solution!其中有一个距离大于汽车加满油能跑的距离！\n"); return; } } for(int i=0,s=0;i<=k;i++){ s += d[i]; if(s > n) { num++; s = d[i]; } } printf("最少加油次数为：%d\n",num); // fp=fopen("output.txt","w"); // fprintf(fp,"%d",num); outfile.open("output.txt",ios::out); outfile<<num<<endl; } int main(){ int i,n,k; int d[1000]; // FILE *fp; //// fp=fopen("input.txt","r"); // fscanf(fp,"%d%d",&n,&k); ifstream cinfile; cinfile.open("input.txt",ios::in); cinfile>>n>>k; printf("汽车加满油后可行驶: %d km\n旅途中加油站个数为: %d \n",n,k); for(i=0;i<=k;i++) cinfile>>d[i]; // fscanf(fp,"%d",&d[i]); greedy(d,n,k); // fclose(fp); cinfile.close(); return 0; }
