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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
лыс
1 / 1 / 0
Регистрация: 04.11.2012
Сообщений: 50
#1

Как просчитать шаги от домов до магазина - C++

10.11.2012, 19:45. Просмотров 739. Ответов 5
Метки нет (Все метки)

Готовлюсь к олимпиаде (уже будет 2 декабря) и на тренировочных курсах попалась такая задача :
Не могу понять, как просчитать шаги от домов до магазина. Может надо вычитать индексы массива?
Кто знает, пожалуйста, приведите код.

Задача C. Дома и магазины
На Новом проспекте построили подряд 10 зданий. Каждое здание может быть либо жилым
домом, либо магазином, либо офисным зданием.
Но оказалось, что жителям некоторых домов на Новом проспекте слишком далеко приходится
идти до ближайшего магазина. Для разработки плана развития общественного транспорта на
Новом проспекте мэр города попросил вас выяснить, какое же наибольшее расстояние приходится
преодолевать жителям Нового проспекта, чтобы дойти от своего дома до ближайшего магазина.

Формат входных данных
Программа получает на вход десять чисел, разделенных пробелами. Каждое число задает тип
здания на Новом проспекте: число 1 обозначает жилой дом, число 2 обозначает магазин, число 0
обозначает офисное здание. Гарантируется, что на Новом проспекте есть хотя бы один жилой дом
и хотя бы один магазин.

Формат выходных данных
Выведите одно целое число: наибольшее расстояние от дома до ближайшего к нему магазина.
Расстояние между двумя соседними домами считается равным 1 (то есть если два дома стоят рядом,
то между ними расстояние 1, если между двумя домами есть еще один дом, то расстояние между
ними равно 2 и т.д.)

Пример
ввод - 2 0 1 1 0 1 0 2 1 2
вывод - 3
В примере из условия дальше всего идти до ближайшего магазина жителям четвертого дома:
ближайший к их дому магазин находится в первом доме, и им нужно пройти три дома до него.
Жителям других домов придется пройти меньшее расстояние до ближайшего магазина, поэтому
ответ 3.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.11.2012, 19:45     Как просчитать шаги от домов до магазина
Посмотрите здесь:

В цикле while просчитать произведение функции и вывести 5 значений - C++
Нужно написать программу, которая будет считать произведение данной функции и выводить 5 значений с применением цикла while. ...

Просчитать и записать периметр и площадь для каждого элемента массива - C++
В общем есть, задание и хотел бы попросить именно помощь в объяснении, а не решении ее. Ну можно ссылочками где почитать если что. Тут...

Просчитать путь прохождение конем шахматной доски (с использованием эвристики доступности) - C++
Изучаю с++, наткнулся в учебнике на задачу - просчитать путь прохождение конем шахматной доски + для хардкорности использовать эвристику...

Просчитать количество вариантов представления числа в виде суммы натуральных цифр 1, 2 и 3 - C++
Дано натуральное число N. Необходимо просчитать количество вариантов представления числа в виде суммы натуральных цифр 1, 2 и 3. К...

Определить количество домов, построенных раньше заданного года - C++
Имеются сведения о домах: количество этажей, год постройки. Создать очередь, вывести ее на экран. Определить количество домов, построенных...

Вычислить количество домов, которое можно построить на площади s1 - C++
Итак, у нас есть значение площади некоторого земельного участка, допустим s1. Еще есть значение площади, которую занимает 1 дом, например...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
11.11.2012, 07:20     Как просчитать шаги от домов до магазина #2
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
#include<iostream>
#include<cmath>
using namespace std;
int main()
{
    int a[10][2], i, j, i_max=-1;
    for(i=0; i<10; i++)
    {
        cin>>a[i][0];
        a[i][1]=20;
    }
    for(i=0; i<10; i++)
        if(a[i][0]==2)
        {
            for(j=0; j<10; j++)
                if(a[j][0]==1 && a[j][1]>abs(i-j))
                    a[j][1]=abs(i-j);
        }
    for(i=0; i<10; i++)
        if(a[i][0]==1)
        {
            if(i_max==-1)
                i_max=i;
            else
                if(a[i][1]>a[i_max][1])
                    i_max=i;
        }
    cout<<a[i_max][1]<<endl;
 
 
    return 0;
}
Kandelyabr
7 / 7 / 0
Регистрация: 03.04.2012
Сообщений: 15
11.11.2012, 18:38     Как просчитать шаги от домов до магазина #3
Цитата Сообщение от valeriikozlov Посмотреть сообщение
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
#include<iostream>
#include<cmath>
using namespace std;
int main()
{
    int a[10][2], i, j, i_max=-1;
    for(i=0; i<10; i++)
    {
        cin>>a[i][0];
        a[i][1]=20;
    }
    for(i=0; i<10; i++)
        if(a[i][0]==2)
        {
            for(j=0; j<10; j++)
                if(a[j][0]==1 && a[j][1]>abs(i-j))
                    a[j][1]=abs(i-j);
        }
    for(i=0; i<10; i++)
        if(a[i][0]==1)
        {
            if(i_max==-1)
                i_max=i;
            else
                if(a[i][1]>a[i_max][1])
                    i_max=i;
        }
    cout<<a[i_max][1]<<endl;
 
 
    return 0;
}
Программа составлена верно лишь в том случае, если на массиве из 10 домов 1 магазин, а в условии сказано, что хотя бы 1 магазин, соответственно при числе магазинов от одного и выше правильный результат будет выводиться для одного, последнего магазина в массиве.

Добавлено через 1 минуту
Эта программа верно считает наименьшее расстояние из наиболее отдалённых домов.
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
#include <iostream>
using namespace std;
 
int k=0, l=0, a = 10;
 
int length(int *buf1, int *buf2) {
    int n[k], m;
    for(int i=0; i<k; i++) {
        n[i] = a;
        for(int j=0; j<l; j++) {
            if(buf1[i] > buf2[j]) m = buf1[i] - buf2[j];
            else
                m = buf2[j] - buf1[i];
            if(m < n[i]) n[i] = m;
        }
    }
    m = 0;
    for(int i=0; i<k; i++) {
        if(n[i] > m) m = n[i];
    }
    return m;
}
 
int main()
{
    int a = 10, town[a], buf1[a - 1], buf2[a - 1];
    for(int i=0; i<a; i++) {
        cin >> town[i];
        if(town[i]==1) {buf1[k] = i; ++k;}
        if(town[i]==2) {buf2[l] = i; ++l;}
    }
    if(k<1) {
        cout << "Error. Number of houses k = " << k << " >= 1.\n";
        return 1;
    }
    if(l<1) {
        cout << "Error. Number of markets l = " << l << " >= 1.\n";
        return 1;
    }
    cout << length(buf1, buf2);
    return 0;
}
valeriikozlov
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
11.11.2012, 19:00     Как просчитать шаги от домов до магазина #4
Цитата Сообщение от Kandelyabr Посмотреть сообщение
Программа составлена верно лишь в том случае, если на массиве из 10 домов 1 магазин, а в условии сказано, что хотя бы 1 магазин, соответственно при числе магазинов от одного и выше правильный результат будет выводиться для одного, последнего магазина в массиве.
тут Вы неправы, результат учитывает абсолютно все имеющиеся магазины.
Kandelyabr
7 / 7 / 0
Регистрация: 03.04.2012
Сообщений: 15
11.11.2012, 19:41     Как просчитать шаги от домов до магазина #5
Прошу извинить, увидел, где ошибся с анализом, недопонял логику.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.11.2012, 20:06     Как просчитать шаги от домов до магазина
Еще ссылки по теме:

Найти количество и тип домов с наибольшим общим количеством квартир - C++
Привет учёным, студентам и программистам! Помогите, пожалуйста! Сам слаб в таких тонкостях. Лучше сразу через исполняемый файл,...

Первые шаги. - C++
Здравствуйте. Извините, может, за тупые вопросы. Но с языком С впервые сталкиваюсь. Использую среду прогр-я C-Free Standard 4.0. Открыл...

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

Первые шаги в программированнии! - C++
Добрые товарищи помогите чайнику в программировании с одной проблемой. Я решил изучить язык програмирования Си++, скачал полную коллекцию...

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

Первые шаги: ничего не получается - C++
Всем привет! Я скачала советуемую здесь на форуме версию wxDev-C++ 7.3.1. Но у меня ничего не получается. Даже на банальном примере из...


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

Или воспользуйтесь поиском по форуму:
лыс
1 / 1 / 0
Регистрация: 04.11.2012
Сообщений: 50
11.11.2012, 20:06  [ТС]     Как просчитать шаги от домов до магазина #6
Запустил на проверку обе программы и обе прошли все 7 тестов из 7. Спасибо, разбираюсь с Вашими алгоритмами.
Yandex
Объявления
11.11.2012, 20:06     Как просчитать шаги от домов до магазина
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru