Интересное задание (Определить стоимость проезда на трамвае)

@boberjajtsegolo · Регистрация: 28.11.2012

Author24 — интернет-сервис помощи студентам

Определить стоимость проезда на трамвае.

Университетское задание для первокурсников, можно сказать первое задание по программированию. По идее, решение должно быть простым, но в голову не приходит ничего путевого (ну не использовать же перебор или не писать же метод для определения кратчайшего пути, но в голову лезут именно такие мысли). У кого какие идеи по решению задачки. Только описывайте алгоритм подробно. Можно и код, и не важно на каком языке, или даже псевдокод.

Задание: Написать программу, которая вычисляет стоимость поездки на трамвае.
Трамвайная сеть имеет следующую структуру:
Существует 5 трамвайных линий, каждая из которых имеет конечную остановку (обозначено красным).
Существует 2 зоны (зеленая область, городская зона; белая микрорайоны). Кроме пяти линий существует еще кольцевой маршрут, который соединяет

между собой каждую вторую остановку каждой из 5 линий.

Остановки обозначаются кодом из двух цифр. Первая цифра обозначает номер линии, вторая номер остановки. Участки дороги, обозначенные пунктиром, закрыты временно на ремонт, по этому не используются.

За каждую поездку берется одноразовый сбор 3 рубля. Если остановки находятся по соседству и проезд между ними не закрыт, стоимость уменьшается до 2 рублей.

Дополнительно берется сбор в 1 рубль за каждое пересечение зон, и за использование конечной станции.

Например:
старт->цель стоимость объяснение
31 -> 32 2 рубля поездка на соседнюю остановку
21 -> 14 4 рубля одноразовый сбор + пересечение границы зон
55 -> 52 5 рублей одноразовый сбор + пересечение границы зон + конечная остановка

@kravam · 28.11.2012, 11:25

Сообщение от boberjajtsegolo

метод для определения кратчайшего пути

нет необходимости писать. При внимательном рассмотрении мы увидим, что каким бы длинным не был путь, стоимость проезда не изменится. Завтра накропаю, а щас всем спать.

Добавлено через 9 часов 29 минут
Хотя нет, я может быть поторопился с предыдущим выводом, ибо 00->01 можно добраться несколькими путями и стоимость будет разная. Но не суть. Всё равно кратчайший маршрут это лишнее. Эту задачу надо решать так:

Имеем (условно):

<две_рядом><две_не_рядом><пересечение_зон><конечная>

Каждую из этих сущностей это назовём "услуга"
Сколько таких услуг мы будем иметь в дороге? Одну или две или три ну и так далее.
Подсчитаем все варианты этих услуг, которые МЫ МОЖЕМ ИМЕТЬ В ДОРОГЕ. Вот они
(Начинаем с одной услуги, потом увеличиваем до двух и так далее)

1 услуга
++++++++++++
<две_рядом>
<две_не_рядом>

2 услуги
++++++++++++
<две_рядом><пересечение_зон>
<две_рядом><конечная>
<две_не_рядом><пересечение_зон>
<две_не_рядом><конечная>

3 услуги
++++++++++++
<две_не_рядом><пересечение_зон><конечная>
<две_не_рядом><пересечение_зон><пересечение_зон>

4 услуги
++++++++++++
<две_не_рядом><пересечение_зон><пересечение_зон><конечная>

5 услуг
++++++++++++
<две_не_рядом><пересечение_зон><пересечение_зон><конечная><конечная>

ВНИМАНИЕ! ДАЛЬШЕ БУДЕТ БАЗИРОВАНИЕ НА ВЫВОДАХ ВЫШЕ! ВРОДЕ ВСЕ ВАРИАНТЫ ПЕРЕБРАЛ, ИСПРАВЛЯЙТЕ, ЕСЛИ ЧТО!

Ну теперь попроще будет. Видим, что там где присутствует услуга <две_рядом>, там нет услуги <две_не_рядом>; Псевдокод:

C++

1 2	if (<две_рядом>) else

Разберёмся с услугой <две рядом>, видим, что если рядом с <две_рядом> может быть только либо <пересечение_зон>, либо <конечная>; только одно из двух. Псевдокод:

C++

if (<две_рядом>)
 if (<пересечение_зон>)
 //Тут не else! Если тут будем писать else, то тогда получится, что варианта
 //<две_рядом> (с одной услугой то бишь) просто-напросто не существует!
 if<конечная>
else

Пусть одна станция X, другая Y. На практике если они <две_рядом> это будет означать

C++

1	((abs (X%10-Y%10))==1)

Так, а пересечение зон будет означать, что:

C++

1	(((X%10)>=3&&(Y%10)<=3)\|\|((X%10)<=3&&(Y%10)>=3))

А использование конечной будет означать

C++

1	((X%10==5)\|\|(Y%10==5))

ВНИМАНИЕ! ЕСЛИ КТО-ТО МОЖЕТ ПРОЩЕ ОПРЕДЕЛИТЬ, НАХОДЯТСЯ ДВЕ СТАНЦИИ РЯДОМ И ЕСТЬ ПЕРЕСЕЧЕНИЕ ЗОН ИЛИ НЕТ И НА СЧЁТ КОНЕЧНОЙ, ПУСТЬ НАПИШУТ ДРУГИЕ УЛОВИЯ!

Имеем псевдокод то есть:

C++

int st_0= X;
int st_1= Y;
int tsena= 0
 
if ((abs (X%10-Y%10))==1) {
 tsena+=2;
 if (((X%10)>=3&&(Y%10)<=3)||((X%10)<=3&&(Y%10)>=3))
  tsena+=1;
 if ((X%10==5)||(Y%10==5))
  tsena+=1;
}
else

Вот так примерно всё это и делается. Два ньюанса: условие, означающее <две_рядом> надо поправить, учитывая, что существуют закрытые перегоны:

C++

1	((abs (X%10-Y%10))==1)&&!((X==21&&Y==00)\|\|(X==00&&Y==21))&&!((X==42&&Y==52)\|\|(X==52&&Y==42))

И помним, что стоимость за использование конечной и за пересечение зон одинаковое; конечный псеводокод:

C++

int st_0= X;
int st_1= Y;
int tsena= 0
 
if ((abs (X%10-Y%10))==1)&&!((X==21&&Y==00)||(X==00&&Y==21))&&!((X==42&&Y==52)||(X==52&&Y==42)) {
 tsena+=2;
 if (((X%10)>=3&&(Y%10)<=3)||((X%10)<=3&&(Y%10)>=3))||((X%10==5)||(Y%10==5))
  tsena+=1;
}
else

Ну вот как-то так; в "else" надо вставить всё что касается <две_не_рядом> ; щас попробую рабочий код написать.

Добавлено через 7 минут
В псевдокодах надо писать так:

C++

1 2	int = X; int = Y;

а не так;

C++

1 2	int st_0= X; int st_1= Y;

Croessmah · 28.11.2012, 11:34

Сообщение от kravam

Пусть одна станция X, другая Y. На практике если они <две_рядом> это будет означать

C++

1	((abs (X%10-Y%10))==1)

Но ведь остановки 12 и 52 не имеют промежуточных узлов.

C++

1	(((X%10)>=3&&(Y%10)<=3)\|\|((X%10)<=3&&(Y%10)>=3))

И тут не понятка...нужно ли учитывать в проезде двойное пересечение зон? То есть, например, чтобы добраться из 25 до 15, нужно сначала въехать в зеленую зону, потом её покинуть - два пересечения. Да и конечных тоже две.

Добавлено через 3 минуты
И еще закрытые пути тоже нужно учесть.

@kravam · 28.11.2012, 12:10

Сообщение от Croessmah

Но ведь остановки 12 и 52 не имеют промежуточных узлов.

значит нужно поправить условие. Могу и ошибиться, я там крупными буквами написал

ВНИМАНИЕ! ЕСЛИ КТО-ТО МОЖЕТ ПРОЩЕ ОПРЕДЕЛИТЬ, НАХОДЯТСЯ ДВЕ СТАНЦИИ РЯДОМ И ЕСТЬ ПЕРЕСЕЧЕНИЕ ЗОН ИЛИ НЕТ И НА СЧЁТ КОНЕЧНОЙ, ПУСТЬ НАПИШУТ ДРУГИЕ УЛОВИЯ!

Сообщение от Croessmah

И тут не понятка...нужно ли учитывать в проезде двойное пересечение зон? То есть, например, чтобы добраться из 25 до 15, нужно сначала въехать в зеленую зону, потом её покинуть - два пересечения. Да и конечных тоже две.

Естессно. Маршрут 15->25 подходит под этот пункт (второй раз пишу), между прочим

5 услуг
++++++++++++
<две_не_рядом><пересечение_зон><пересечение_зон><конечная><конечная>

Так, всё, что касается <две_рядом> я не рассматривал, я это оговорил. Пусть автор рассматривает.

И еще закрытые пути тоже нужно учесть.

учёл вроде

Сообщение от kravam

Два ньюанса: условие, означающее <две_рядом> надо поправить, учитывая, что существуют закрытые перегоны:

@BumerangSP · 28.11.2012, 13:01

Я вот тут нигде матрицы смежности не вижу. Граф же. Тогда сразу станет видно, где у кого какие связи.

@kravam · 28.11.2012, 13:20

Тестируй, результаты сюда. Файл для лучшего понимания ниже кода

C++

#include <stdio.h>
#include <math.h>
#define X array[i][0]
#define Y array[i][1]
 
 
int main () {                                                              
 
 int tsena;
 bool dve_ne_radom= false;
 
 //Сюда пихай значения и тестируй
 #define kol_vo_strochek 3
 int array [][2]= {{21, 52},{33, 44},{22, 45}};
 
 
 
 for (int i= 0; i < kol_vo_strochek; i++) {
 tsena= 0;
                                //<две_рядом>                
 if (((((fabs (X%10-Y%10))==1)&&(X/10==Y/10))||((fabs(X-Y)==10)&&(X%10==2))) &&!((X==21&&Y==00)||(X==00&&Y==21))&&!((X==42&&Y==52)||(X==52&&Y==42))) 
 {
               tsena+=2;
                               //<пересечение_зон||<конечная>
           if ((((X%10)>=3&&(Y%10)<=3)||((X%10)<=3&&(Y%10)>=3))||((X%10==5)||(Y%10==5)))
               tsena+=1;
 }
                                //<две_не_рядом>             
 else 
 {
           dve_ne_radom= true;                     
               tsena+=3;
 }
 
         //К этому моменту мы имеем: <две_рядом> или <две_не_рядом>. Одно из двух: 
         //Если <две_рядом>, опускаем код ниже, если <две_не_рядом> заходим в него
 printf ("\n+|||||  %d\n", tsena);
 if (dve_ne_radom) {
 
                               //Двойное пересечение          
           if ((X%10>=3)&& (Y%10>=3) && (X/10)!=(Y/10)) {                    
               tsena+=2;
               
                               //одна остановка конечная       
               if (X%10==5)  
               tsena+=2;
                               //другая остановка конечная     
               if (Y%10==5)  
               tsena+=2;
           }   
           
                               //а тут нет двойного пересечения
                               //тут есть одинарное пересечение
                               //и конечная остановка; за всё  
                               //по рублю                      
           else {
               if (((X%10)>=3&&(Y%10)<=3)||((X%10)<=3&&(Y%10)>=3))
               tsena+=1;
               
               if ((X%10==5)||(Y%10==5))
               tsena+=1;
           }
 }
 
 printf ("tsena= %d\n", tsena); 
 }
 
 getchar ();
 
 
}

Кликните здесь для просмотра всего текста

<две_рядом>

/////////////////////////////////////////////////////////////////////

<две_рядом><пересечение_зон>
<две_рядом><конечная>

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

<две_не_рядом>

/////////////////////////////////////////////////////////////////////

<две_не_рядом><двойное_пересечение_зон>
<две_не_рядом><двойное_пересечение_зон><конечная>
<две_не_рядом><двойное_пересечение_зон><конечная><конечная>
______________________________________________________________________

<две_не_рядом><пересечение_зон>
<две_не_рядом><пересечение_зон><конечная>
<две_не_рядом><конечная>

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

Добавлено через 56 секунд

Кликните здесь для просмотра всего текста

<две_рядом>

/////////////////////////////////////////////////////////////////////

<две_рядом><пересечение_зон>
<две_рядом><конечная>

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

<две_не_рядом>

/////////////////////////////////////////////////////////////////////

<две_не_рядом><двойное_пересечение_зон>
<две_не_рядом><двойное_пересечение_зон><конечная>
<две_не_рядом><двойное_пересечение_зон><конечная><конечная>
______________________________________________________________________

<две_не_рядом><пересечение_зон>
<две_не_рядом><пересечение_зон><конечная>
<две_не_рядом><конечная>

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

Добавлено через 58 секунд
фигня какая-то не удаётся что-то мне сжать это содержание.

C++

<две_рядом>
 
/////////////////////////////////////////////////////////////////////
 
<две_рядом><пересечение_зон>
<две_рядом><конечная>
 
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 
<две_не_рядом>
 
/////////////////////////////////////////////////////////////////////
 
 
<две_не_рядом><двойное_пересечение_зон>
<две_не_рядом><двойное_пересечение_зон><конечная>
<две_не_рядом><двойное_пересечение_зон><конечная><конечная>
______________________________________________________________________
 
<две_не_рядом><пересечение_зон>
<две_не_рядом><пересечение_зон><конечная>
<две_не_рядом><конечная>
 
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

@boberjajtsegolo · 30.11.2012, 19:29 **[ТС]**

Спасибо большое за помощь, я просмотрел код, уловил мысль, написал сам программу и потом рассмотрел Ваш код детально и сравнил со своим. Я немного по другому if инструкции написал но булевы выражения по сути те же.
Выложу и свой код, может кому то еще пригодится, но выложу на Java.

Java

class  Tsena_beleta{  
  public static void main(String[]arg){
    int x = In.readInt();//класс In не стандартный а упрощенный класс для новичков взятый из одной книги
    int y = In.readInt();
    int tsena = 0;
 
    if ((((Math.abs(x%10 - y%10))==1) & ((x!=0 & y!=21)|(y!=21 & x!=0))) | (((x%10 == 2) & (y%10 == 2))& ((x!=42&y!=52)|(y!=52&x!=42))&(x!=y))){
      tsena = tsena + 2;
      System.out.println("Соседние остановки");
    }else {
      tsena = tsena + 3;
      System.out.println("Одноразовый сбор");
    }
    if(x%10==5){
      tsena = tsena + 1;
      System.out.println("Конечная");
    }
    if(y%10==5){
      tsena = tsena + 1;
      System.out.println("Конечная");
    }
    if(((x%10 <= 2)&(y%10>2))|((y%10 <= 2)&(x%10>2))){
      tsena = tsena + 1;
      System.out.println("1xПересечение зон");
    }
    if((x/10 != y/10) & x%10>2 & y%10>2){
      tsena = tsena + 2;
      System.out.println("2xПересечение зон");
    }
    System.out.println(tsena);
  }
}

@boberjajtsegolo 35 / 35 / 4 Регистрация: 28.11.2012 Сообщений: 164
		1
	Интересное задание (Определить стоимость проезда на трамвае) 28.11.2012, 00:31. Показов 1269. Ответов 6 Метки нет (Все метки) Определить стоимость проезда на трамвае. Университетское задание для первокурсников, можно сказать первое задание по программированию. По идее, решение должно быть простым, но в голову не приходит ничего путевого (ну не использовать же перебор или не писать же метод для определения кратчайшего пути, но в голову лезут именно такие мысли). У кого какие идеи по решению задачки. Только описывайте алгоритм подробно. Можно и код, и не важно на каком языке, или даже псевдокод. Задание: Написать программу, которая вычисляет стоимость поездки на трамвае. Трамвайная сеть имеет следующую структуру: Существует 5 трамвайных линий, каждая из которых имеет конечную остановку (обозначено красным). Существует 2 зоны (зеленая область, городская зона; белая микрорайоны). Кроме пяти линий существует еще кольцевой маршрут, который соединяет между собой каждую вторую остановку каждой из 5 линий. Остановки обозначаются кодом из двух цифр. Первая цифра обозначает номер линии, вторая номер остановки. Участки дороги, обозначенные пунктиром, закрыты временно на ремонт, по этому не используются. За каждую поездку берется одноразовый сбор 3 рубля. Если остановки находятся по соседству и проезд между ними не закрыт, стоимость уменьшается до 2 рублей. Дополнительно берется сбор в 1 рубль за каждое пересечение зон, и за использование конечной станции. Например: старт->цель стоимость объяснение 31 -> 32 2 рубля поездка на соседнюю остановку 21 -> 14 4 рубля одноразовый сбор + пересечение границы зон 55 -> 52 5 рублей одноразовый сбор + пересечение границы зон + конечная остановка Миниатюры 0

@kravam быдлокодер 1724 / 911 / 106 Регистрация: 04.06.2008 Сообщений: 5,686
	28.11.2012, 12:10	4
	Сообщение от Croessmah Но ведь остановки 12 и 52 не имеют промежуточных узлов. значит нужно поправить условие. Могу и ошибиться, я там крупными буквами написал ВНИМАНИЕ! ЕСЛИ КТО-ТО МОЖЕТ ПРОЩЕ ОПРЕДЕЛИТЬ, НАХОДЯТСЯ ДВЕ СТАНЦИИ РЯДОМ И ЕСТЬ ПЕРЕСЕЧЕНИЕ ЗОН ИЛИ НЕТ И НА СЧЁТ КОНЕЧНОЙ, ПУСТЬ НАПИШУТ ДРУГИЕ УЛОВИЯ! Сообщение от Croessmah И тут не понятка...нужно ли учитывать в проезде двойное пересечение зон? То есть, например, чтобы добраться из 25 до 15, нужно сначала въехать в зеленую зону, потом её покинуть - два пересечения. Да и конечных тоже две. Естессно. Маршрут 15->25 подходит под этот пункт (второй раз пишу), между прочим 5 услуг ++++++++++++ <две_не_рядом><пересечение_зон><пересечение_зон><конечная><конечная> Так, всё, что касается <две_рядом> я не рассматривал, я это оговорил. Пусть автор рассматривает. И еще закрытые пути тоже нужно учесть. учёл вроде Сообщение от kravam Два ньюанса: условие, означающее <две_рядом> надо поправить, учитывая, что существуют закрытые перегоны: 1

@BumerangSP 4311 / 1422 / 463 Регистрация: 16.12.2010 Сообщений: 2,939 Записей в блоге: 3
	28.11.2012, 13:01	5
	Я вот тут нигде матрицы смежности не вижу. Граф же. Тогда сразу станет видно, где у кого какие связи. 0