VPF::[C]Задача "Треугольник" ("Золотая гора")

FK2703

Дата 16.12.2007, 13:54 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 5
Регистрация: 16.12.2007

Репутация: нет
Всего: нет

очень прошу помощи с задачей "Золотая гора" ("Треугольник") на C

Входной файл input.txt
Выходной: output.txt

Идея-подсказка, предложенная мне: "Реализация проста-делай двумерный массив и пускай цикл снизу. Последняя строка совпадает с исходной, а дальше подымайся вверх и выбирай максимум из двух. a[0][0] твой ответ"

Пример правильного input.txt:
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

Первое число во входном файле (5) - количество строк в треугольнике. Соответственно, остальные - его заполнение. Надо найти сумму чисел, расположенных на пути, начинающемся в верхней точке треугольника и заканчивающимся на основании.
Условия:
1. Каждый шаг на пути может осуществляться вниз по диагонали влево или вниз по диагонали вправо.
2. Число строк в треугольнике - от 1 до 100
3. Треугольник составлен из простых чисел от 0 до 99

Выходные данные.
В файл output.txt записывается только наибольшая сумма в виде целого числа. Для треугольника из примера правильно работающая прога запишет: "30"

Если не сдам в понедельник - не допустят до сессии, хотя это - последний оставшийся зачёт(

zkv

Дата 16.12.2007, 14:12 (ссылка)

(нет голосов)

Загрузка ...

Профиль
Группа: Участник Клуба
Сообщений: 2133
Регистрация: 23.7.2006
Где: Санкт-Петербург

Репутация: 21
Всего: 92

Цитата(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

не простые числа

Добавлено через 47 секунд
вернее не все из них простые

FK2703

Дата 19.12.2007, 00:34 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 5
Регистрация: 16.12.2007

Репутация: нет
Всего: нет

знаю, что не простые. НО в задаче такое условие и этот пример. Думаю, что на слово "простые" надо закрывать глаза

FK2703

Дата 20.12.2007, 22:37 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 5
Регистрация: 16.12.2007

Репутация: нет
Всего: нет

люди, нид хелп.... очень! Есть даж код, но надо поправить так, чтобы прога из текстового файла могла брать одно- и двухразрядные числа, разделённые пробелами!

Код


#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;
}

Это сообщение отредактировал(а) zkv - 21.12.2007, 01:01

kali

Дата 20.12.2007, 23:39 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 139
Регистрация: 9.11.2006
Где: Минск

Репутация: 18
Всего: 20

Это задача с международной олимпиады по информатике 1994 года. День первый, задача первая.

У меня есть решение на паскале. Сча если сильно лениво не будет в си перекидаю.

Код


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.

--------------------

Работая над решением задачи, всегда полезно знать ответ.

kali

Дата 21.12.2007, 01:25 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 139
Регистрация: 9.11.2006
Где: Минск

Репутация: 18
Всего: 20

Код


#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;
}

--------------------

Работая над решением задачи, всегда полезно знать ответ.

FK2703

Дата 21.12.2007, 02:29 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 5
Регистрация: 16.12.2007

Репутация: нет
Всего: нет

kali, спасибо!!! smile

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »