Форум программистов [Powered by Invision Power Board]

Цитата(FK2703 @ 16.12.2007, 13:54

)

3. Треугольник составлен из простых чисел от 0 до 99

Цитата(FK2703 @ 16.12.2007, 13:54

)

7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

Код


#include "stdafx.h"
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>

/*
разбор пути идет снизу, с предпоследней строки.
*/
int *lines[100];
int line;
int elem;
int inside = 0;

int function(int line, int elem)
{
    int sum_left = lines[line][elem] + lines[line+1][elem];
    int sum_right = lines[line][elem] + lines[line+1][elem+1]; 
    int max = sum_left > sum_right ? sum_left : sum_right;
    return max;
}
int recursion()
{
    inside++;
    lines[line][elem] = function(line, elem);
    if (elem+1>line) 
    {
        line--;
        elem=0;
    }else
        elem++;
    if (line==0 && elem==0) return 0;
    recursion();
    return 0;
}
int main(int argc, char* argv[])
{
    int i=0, j=0, a=0, b=0;
    char string[1000];
    int count_lines;

//>>>прочитаем данные из файла
    FILE *file = fopen("in.txt","r");
    fgets (string , 100 , file);
    sscanf(string, "%d", &count_lines); 
    for (i=0; i<count_lines; i++)
    {
        lines[i] = new int[i+1];
        fgets (string , 100 , file);
        for (int j=0; j<i+1; j++)
        {
            lines[i][j] = string[j]-48; 
        }
    }
    fclose(file);
//<<<


//>>>вызов ф-ции подсчета максимальной суммы
line = count_lines-2;
    elem = 0;
    recursion();
    int sum = lines[0][0] + lines[1][0];
//<<<

//>>>освобождение динамически выделенной памяти
    for (i=0; i<count_lines; i++)
        delete lines[i];
//<<<

//>>>вывод результата в файл
    file = fopen("output.txt","w");
    sprintf(string, "%d", sum);
    fputs(string,file);
    fclose (file);


    printf ("%d", inside);
    //<<<
    getch();
    return 0;
}

Код


program triangle;

var
  f:text;
  n:integer;
  tr :array [1..100,1..100] of integer;
  i,j:integer;

procedure readdata;
begin
  assign(f,'input.txt');
  reset(f);
  read(f,n);
  for i:=1 to n do
  begin
    for j:=1 to i do
    begin
      read(f,tr[i,j]);
    end;
  end;
  close(f);
end;

function max(a,b:integer):integer;
begin
  if a>b then max:=a else max:=b;
end;

procedure solve;
begin
  for i:=n downto 1 do
  begin
    for j:=1 to i do
    begin
      if i<>n then tr[i,j]:=tr[i,j]+max(tr[i+1,j],tr[i+1,j+1]);
    end;
  end;
end;

procedure writedata;
begin
  assign(f,'output.txt');
  rewrite(f);
  write(f,tr[1,1]);
  close(f);
end;


begin
  readdata;
  solve;
  writedata;
end.

Код


#include <stdio.h>

FILE *f;
int n;
int tr[100][100];
int i,j;

void readdata() {
  f=fopen("input.txt","r");
  fscanf(f,"%d",&n);
  for(i=0;i<n;i++) {
    for(j=0;j<=i;j++) {
      fscanf(f,"%d",&tr[i][j]);
    };
  };
  fclose(f);
};

int max(int a,int b) {
  if (a>b) {return a;} else {return b;};
};

void solve() {
  for (i=n-1;i>=0;i--) {
    for (j=0;j<=i;j++) {
      if (i!=n-1) { tr[i][j]=tr[i][j]+max(tr[i+1][j],tr[i+1][j+1]);};
    };
  };
};

void writedata() {
  f=fopen("output.txt","w");
  fprintf (f,"%d", tr[0][0]);
  fclose(f);
};


int main(int argc, char* argv[])
{
    readdata();
    solve();
    writedata();
    return 0;
}