Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.67/6: Рейтинг темы: голосов - 6, средняя оценка - 4.67
0 / 0 / 0
Регистрация: 28.11.2015
Сообщений: 10
1

Построить парники, закрывающие огурцы

28.11.2015, 11:11. Просмотров 1090. Ответов 17
Метки нет (Все метки)

Нужно помочь с задачей.
Задачу сдавать на зачёт, я не знаю как её сделать; она мне кажется очень сложной. Пишу на С++
Задача о огурцах.
/////
Задано поле n x m квадратных ячеек, в каждой из которых могут находиться посадки огурцов.
Необходимо построить парники, закрывающие огурцы. Парники могут быть только прямоугольной формы, только со сторонами,
параллельными сторонам поля. Стоимость строительства одного парника складывается из двух составляющих - известной постоянной
и величины,
пропорциональной площади парника. Парник может накрывать только целое количество ячеек. Выяснить какие варианты
строительства парников наименее затратны при условии,
что закрытыми от непогоды оказываются все ячейки с огурцами.
//////
Мне хотя бы подсказочку с алгоритмом, я вообще вообразить не могу как сделать, хотя бы перебором, так как лучшим вариантом может быть вариант с разными по площади парниками. На вход подаются:
S - цена за клетку 1х1
C - цена за строительство 1 парника
и поле с огурцами в виде нулей и единиц(1 - есть). В общем спасибо заранее.
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
28.11.2015, 11:11
Ответы с готовыми решениями:

Работа с одномерными массивами. Коротышки собирали огурцы
Здравствуйте.Не могу понять, почему неправильно считает число максимумов и остаток.Помогите! Сама...

Моё котэ ест огурцы
OMrT3Gi_vs4

Марсианские парники не только возможны, но и эффективнее земных
Будущие покорители Марса могли бы питаться тем, что привезут с Земли, и использовать сложные...

Открыть файл, найти в нём все открывающие и закрывающие скобки и заменить их на begin и end
Необходимо открыть в файл, найти в нём все открывающие и закрывающие скобки и заменить их на begin...

17
6913 / 5978 / 2709
Регистрация: 14.04.2014
Сообщений: 25,504
28.11.2015, 11:18 2
Если поле прямоугольное, то одного парника не хватит, что ли?
0
0 / 0 / 0
Регистрация: 28.11.2015
Сообщений: 10
28.11.2015, 11:55  [ТС] 3
Пусть поле NxM, тогда если всё замостить парниками цена будет S*N*M+C что не является минимальной(минимальна только в случае когда пользователь укажет S = 0)
0
48 / 48 / 6
Регистрация: 24.12.2009
Сообщений: 493
28.11.2015, 12:05 4
Допустим поле = 4x3, тогда число ячеек 12.
Наш Коэф. =1000руб. За все поле 12000. Если с огурцами только 3 ячейки, тогда 3000руб.

Мин. цена = мин. ячейке, т.е. 1000руб. Не ????
0
0 / 0 / 0
Регистрация: 28.11.2015
Сообщений: 10
28.11.2015, 12:11  [ТС] 5
Нет, у нас ещё учитывается цена за СТРОИТЕЛЬСТВО, так может получиться, что выгодней построить один парник чтобы закрыть 4 клетки при этом закрыв 2 - 3 огурца(цена будет 4S+C), чем строить каждый отдельно, так как цена будет равна 3S+3C. Тут не всё так просто на самом деле.

Добавлено через 49 секунд
Нет, у нас ещё учитывается цена за СТРОИТЕЛЬСТВО, так может получиться, что выгодней построить один парник чтобы закрыть 4 клетки при этом закрыв 2 - 3 огурца(цена будет 4S+C), чем строить каждый отдельно, так как цена будет равна 3S+3C. Тут не всё так просто на самом деле.
0
538 / 346 / 206
Регистрация: 27.11.2014
Сообщений: 1,043
28.11.2015, 12:33 6
Мне это нравится. Ей богу. Я пока все думаю.
0
48 / 48 / 6
Регистрация: 24.12.2009
Сообщений: 493
28.11.2015, 12:48 7
Нам дали поле с расположением ячеек с огурцами. Мы это поле берем, как 2-х мерн. массив. Считаем кол-во занятых ячеек, прибавляем наш коэф. + за строительство:

C++ (Qt)
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>
 
using namespace std;
 
int main()
{
    char field[4][3] = {'*', '*', ' ',
                        ' ', ' ', ' ',
                        ' ', '*', ' ',
                        ' ', '*', ' '};//pole 4x3
    int S=0;//ploshad
    int priceK1 = 1000;//koeficient za ploshad
    int priceK2 = 10000;//koef za stroitelstvo
    int sumPrice;//cena itogo
 
    for(int i=0; i<3;i++)
    {
        for(int j=0; j<4; j++)
        {
                if(field[i][j] == '*')
                {
                    S++;
                }
        }
    }
 
    sumPrice = S*priceK1+priceK2;
 
    cout << sumPrice;
 
    return 0;
}
Так не годится ?

Добавлено через 5 минут
Тут не площадь конечно, а ячейки, но в задаче же сказано про кол-во занятых ячеек. Вот мы их и учитываем.

Добавлено через 1 минуту
Поле же можно разбить на квадраты ?

Добавлено через 2 минуты
Я спать
0
0 / 0 / 0
Регистрация: 28.11.2015
Сообщений: 10
28.11.2015, 14:07  [ТС] 8
Ну и что ты сделал? Программа явно лажа.
строка 27: Ты построил парников столько сколько огурцов, но почему-то прибавляешь priceK2 один раз.
И тем более ты просто построил на каждый огурец 1 парник - это явно не решение. Так как зависит от цен. Нужно подобрать ОПТИМАЛЬНОЕ по стоимости.

Добавлено через 55 секунд
Напишите о успехах. пожалуйста.
0
4454 / 2072 / 263
Регистрация: 01.03.2013
Сообщений: 5,508
Записей в блоге: 22
28.11.2015, 15:14 9
Лучший ответ Сообщение было отмечено Faragor как решение

Решение

Так прошлый раз баклажаны были же вроде... с "праниками"... Какие варианты строительства праников наименее затратны

ЗЫ а вообще, задачка интересная, да.
1
48 / 48 / 6
Регистрация: 24.12.2009
Сообщений: 493
28.11.2015, 15:30 10
_Ivana, а мне нравится реализация с квадратами. Разбиваешь поле на квадраты. Минимальное кол-во - это площадь всего поля. В примере 4x3 - 12 квадратов. И ввести понятие масштаб. Т.е из 12 при желании можно сделать 48, из 48 можно сделать 96.... Так до тех пор, пока в клетки не уместятся все огурцы\баклажаны.

В изм. площади нужда отпадает, т.к. исп. квадраты, а результат тот же.
0
4454 / 2072 / 263
Регистрация: 01.03.2013
Сообщений: 5,508
Записей в блоге: 22
28.11.2015, 15:35 11
ilja123, я не понял вашу идею с квадратами, но тут существует очень простой тест - проверить ваше и мое решение на нескольких входных данных и сравнить результаты. У меня по умолчанию "праники" не накладываются друг на друга, но можно поменять пару символов в коде и будет возможность поиска решения как с возможностью наложения, так и без.
0
0 / 0 / 0
Регистрация: 28.11.2015
Сообщений: 10
28.11.2015, 16:27  [ТС] 12
Там на Haskell щас буду разбираться, если работает, то я самый счастливый человек в мире!
0
_Ivana
28.11.2015, 16:28
  #13

Не по теме:

Если разберешься (не в алгоритме, а в коде), то тоже есть повод порадоваться :)

0
0 / 0 / 0
Регистрация: 28.11.2015
Сообщений: 10
29.11.2015, 00:20  [ТС] 14
Преподаватель очень требовательный. Вряд ли.
0
538 / 346 / 206
Регистрация: 27.11.2014
Сообщений: 1,043
29.11.2015, 10:34 15
Если потерпишь недельку, то мы успеем пройти на след неделе динамическое программирование.
0
0 / 0 / 0
Регистрация: 28.11.2015
Сообщений: 10
29.11.2015, 11:01  [ТС] 16
Ну у меня ещё 3 недели до него.
0
0 / 0 / 0
Регистрация: 28.11.2015
Сообщений: 10
30.11.2015, 17:08  [ТС] 17
Не могли бы вы объяснить алгоритм?
0
0 / 0 / 0
Регистрация: 17.05.2016
Сообщений: 4
17.05.2016, 11:08 18
Пусть поле NxM, тогда если всё замостить парниками цена будет S*N*M+C что не является минимальной(минимальна только в случае когда пользователь укажет S = 0)
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
17.05.2016, 11:08

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

Нужно построить график функций, вычислить и построить диаграмму и сделать легенду.
http://rghost.ru/private/51147973/42d3fdac651f8296a3ad0c7b14f1686e Нужно построить график...

Построить на символьном экране чертеж: в треугольной пирамиде построить сечение параллельное основанию
Построить на символьном экране чертеж: в треугольной пирамиде построить сечение параллельное...

построить асимптотик и проверить на сходимость задачу коши с малым параметром и построить графики.
помогите решить оду с малым параметром на маткаде и построить график,очень надо,срочно!...

Как построить оси координат на picturebox и на этих осях построить график функции
Здравствуйте, в общем не могу разобраться как построить оси координат на picturebox и на этих осях...


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

Или воспользуйтесь поиском по форуму:
18
Ответ Создать тему
Опции темы

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