Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
boberjajtsegolo
34 / 34 / 3
Регистрация: 28.11.2012
Сообщений: 164
28.11.2012, 00:31     Интересное задание (Определить стоимость проезда на трамвае) #1
Определить стоимость проезда на трамвае.

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

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

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

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

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

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

Например:
старт->цель стоимость объяснение
31 -> 32 2 рубля поездка на соседнюю остановку
21 -> 14 4 рубля одноразовый сбор + пересечение границы зон
55 -> 52 5 рублей одноразовый сбор + пересечение границы зон + конечная остановка
Миниатюры
Интересное задание (Определить стоимость проезда на трамвае)  
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.11.2012, 00:31     Интересное задание (Определить стоимость проезда на трамвае)
Посмотрите здесь:

[C++] Определить общую стоимость оборудования за n лет C++
C++ Интересное задание (Сколько ячеек памяти выделится под переменные?)
C++ Разработать программу «Стоимость компьютера», позволяющую вычислять стоимость комплекта для АРМ различных специалистов
Разработать программу «Стоимость компьютера», позволяющую вычислять стоимость комплекта для АРМ различных специалистов C++
C++ Зная стоимость каждой единицы оборудования, определить суммарную стоимость и кол-во единиц оборуд-я, проработавших > 10 лет
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
kravam
быдлокодер
 Аватар для kravam
1512 / 872 / 44
Регистрация: 04.06.2008
Сообщений: 5,271
28.11.2012, 11:25     Интересное задание (Определить стоимость проезда на трамвае) #2
Цитата Сообщение от boberjajtsegolo Посмотреть сообщение
метод для определения кратчайшего пути
нет необходимости писать. При внимательном рассмотрении мы увидим, что каким бы длинным не был путь, стоимость проезда не изменится. Завтра накропаю, а щас всем спать.

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

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

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

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

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

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

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

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

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

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

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

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

C++
1
2
3
4
5
6
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++
1
2
3
4
5
6
7
8
9
10
11
12
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++
1
2
3
4
5
6
7
8
9
10
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
Модератор
Эксперт С++
 Аватар для Croessmah
11825 / 6804 / 769
Регистрация: 27.09.2012
Сообщений: 16,871
Записей в блоге: 2
Завершенные тесты: 1
28.11.2012, 11:34     Интересное задание (Определить стоимость проезда на трамвае) #3
Цитата Сообщение от 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
быдлокодер
 Аватар для kravam
1512 / 872 / 44
Регистрация: 04.06.2008
Сообщений: 5,271
28.11.2012, 12:10     Интересное задание (Определить стоимость проезда на трамвае) #4
Цитата Сообщение от Croessmah Посмотреть сообщение
Но ведь остановки 12 и 52 не имеют промежуточных узлов.
значит нужно поправить условие. Могу и ошибиться, я там крупными буквами написал
ВНИМАНИЕ! ЕСЛИ КТО-ТО МОЖЕТ ПРОЩЕ ОПРЕДЕЛИТЬ, НАХОДЯТСЯ ДВЕ СТАНЦИИ РЯДОМ И ЕСТЬ ПЕРЕСЕЧЕНИЕ ЗОН ИЛИ НЕТ И НА СЧЁТ КОНЕЧНОЙ, ПУСТЬ НАПИШУТ ДРУГИЕ УЛОВИЯ!
Цитата Сообщение от Croessmah Посмотреть сообщение
И тут не понятка...нужно ли учитывать в проезде двойное пересечение зон? То есть, например, чтобы добраться из 25 до 15, нужно сначала въехать в зеленую зону, потом её покинуть - два пересечения. Да и конечных тоже две.
Естессно. Маршрут 15->25 подходит под этот пункт (второй раз пишу), между прочим

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

И еще закрытые пути тоже нужно учесть.
учёл вроде
Цитата Сообщение от kravam Посмотреть сообщение
Два ньюанса: условие, означающее <две_рядом> надо поправить, учитывая, что существуют закрытые перегоны:
BumerangSP
 Аватар для BumerangSP
4283 / 1405 / 121
Регистрация: 16.12.2010
Сообщений: 2,941
Записей в блоге: 3
28.11.2012, 13:01     Интересное задание (Определить стоимость проезда на трамвае) #5
Я вот тут нигде матрицы смежности не вижу. Граф же. Тогда сразу станет видно, где у кого какие связи.
kravam
быдлокодер
 Аватар для kravam
1512 / 872 / 44
Регистрация: 04.06.2008
Сообщений: 5,271
28.11.2012, 13:20     Интересное задание (Определить стоимость проезда на трамвае) #6
Тестируй, результаты сюда. Файл для лучшего понимания ниже кода
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#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++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
<две_рядом>
 
/////////////////////////////////////////////////////////////////////
 
<две_рядом><пересечение_зон>
<две_рядом><конечная>
 
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 
<две_не_рядом>
 
/////////////////////////////////////////////////////////////////////
 
 
<две_не_рядом><двойное_пересечение_зон>
<две_не_рядом><двойное_пересечение_зон><конечная>
<две_не_рядом><двойное_пересечение_зон><конечная><конечная>
______________________________________________________________________
 
<две_не_рядом><пересечение_зон>
<две_не_рядом><пересечение_зон><конечная>
<две_не_рядом><конечная>
 
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.11.2012, 19:29     Интересное задание (Определить стоимость проезда на трамвае)
Еще ссылки по теме:

C++ Придумайте, пожалуйста, задание с классами - только интересное
C++ Разветвляющийся алгоритм. Определить размеры очередей после проезда маршрутного такси заданной вместимости
C++ Определить стоимость приобретенных путевок

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
boberjajtsegolo
34 / 34 / 3
Регистрация: 28.11.2012
Сообщений: 164
30.11.2012, 19:29  [ТС]     Интересное задание (Определить стоимость проезда на трамвае) #7
Спасибо большое за помощь, я просмотрел код, уловил мысль, написал сам программу и потом рассмотрел Ваш код детально и сравнил со своим. Я немного по другому if инструкции написал но булевы выражения по сути те же.
Выложу и свой код, может кому то еще пригодится, но выложу на Java.
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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);
  }
}
Yandex
Объявления
30.11.2012, 19:29     Интересное задание (Определить стоимость проезда на трамвае)
Ответ Создать тему
Опции темы

Текущее время: 13:55. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru