Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.93/15: Рейтинг темы: голосов - 15, средняя оценка - 4.93
 Аватар для DaskOFF
113 / 113 / 42
Регистрация: 02.05.2012
Сообщений: 524
Записей в блоге: 1

В правильном ли направлении я иду? (Разработать программу для составления списка заданий для параллельных процессоров)

23.07.2013, 21:53. Показов 3468. Ответов 25
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Есть задачка:
Разработать программу для составления списка заданий для параллельных процессоров. Три одинаковых центральных процессора могут выполнять М заданий. Каждое задание может быть выполнено на любом процессоре, и, если задание загружено в процессор, оно находится в нем до полного завершения(т.е. задания не могут прерываться или разделяться между процессорами). При i=1,..,M задание i требует ti времени для его выполнения. Определить оптимальный порядок заданий, т.е. такой, который дает возможность завершить все задания в кратчайшее время.
Я прикинул, и у меня есть 2 способа решения задачи, но 1 долгий, а второй рассматривает не все варианты.
1) Полный перебор перестановок, и вывод только тех последовательностей, время выполнения которых минимально, но допустим при 14 задачах мы имеем 87 178 291 200 вариантов последовательностей и они будут очень долго перебираться.

2) Я вручную просмотрел и пришел к тому, что можно просто отсортировать массив по невозрастанию и по порядку добавлять задачи в первый освобождающийся процессор, но тут мы получим только одну последовательность, а все остальные получатся, если выполнить все перестановки с задачами, время выполнения которых одинаково.

Вопрос в том, правилен ли второй способ(или я что-то упустил)?
И будет ли это считаться решением задачи(ведь вроде не говорится, что требуется найти все последовательности)?
0
Лучшие ответы (1)
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
23.07.2013, 21:53
Ответы с готовыми решениями:

Разработать программу для составления списка неуспевающих студентов
Разработать программу для составления списка неуспевающих студентов. Текст документа я написал а вот программу немогу написать. Помогите...

Разработать программу для составления итоговой ведомости, в которой итоговая оценка по предмету равна средне-арифмитической по трем циклам
Разработать программу для составления итоговой ведомости, в которой итоговая оценка по предмету равна средне-арифмитической по трем циклам....

Разработать приложение для автоматизации составления тестов
Разработать приложение для автоматизации составления тестов: Пароль: 123 Помогите пожалуйста сделать 1) сложение строк с...

25
194 / 174 / 30
Регистрация: 10.07.2012
Сообщений: 800
25.07.2013, 20:18
Студворк — интернет-сервис помощи студентам
Цитата Сообщение от DaskOFF Посмотреть сообщение
может еще посоветуете какие-нибудь книги, чтобы полностью разобраться с темой таких задач?
почитайте о динамическом программировании. до конца жизни будет, чем заняться...)
1
 Аватар для DaskOFF
113 / 113 / 42
Регистрация: 02.05.2012
Сообщений: 524
Записей в блоге: 1
25.07.2013, 21:18  [ТС]
Цитата Сообщение от salam Посмотреть сообщение
почитайте о динамическом программировании. до конца жизни будет, чем заняться...)
ну я приметил книгу, которую тут посоветовали ранее (Стивен Скиена. Алгоритмы.) Хороший выбор? Я только 1 курс закончил, но очень переживаю за свое будущее т.к. подобные алгоритмы мне пока даются не очень легко
Я ее пока просто полистал, а прочитал только "Задача о разбиении", но как я понял мне надо разбивать и переставлять, т.к. упорядоченное разбиение мне ничего толком не даст
0
1406 / 648 / 135
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
25.07.2013, 21:56
Цитата Сообщение от DaskOFF Посмотреть сообщение
т.к. подобные алгоритмы мне пока даются не очень легко
чтобы понять такие алгоритмы нужно прорешать задач 100. Они (кого я знаю лично) никому легко не давались. Не парься.
1
 Аватар для DaskOFF
113 / 113 / 42
Регистрация: 02.05.2012
Сообщений: 524
Записей в блоге: 1
18.08.2013, 19:22  [ТС]
Цитата Сообщение от Thinker Посмотреть сообщение
В книге
Стивен Скиена. Алгоритмы.
эта задача в главе "Динамическое программирование"
Задача разбиения ?
0
Эксперт С++
 Аватар для Thinker
4267 / 2241 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
21.08.2013, 13:22
Цитата Сообщение от DaskOFF Посмотреть сообщение
Задача разбиения ?
да, разбиение
0
 Аватар для DaskOFF
113 / 113 / 42
Регистрация: 02.05.2012
Сообщений: 524
Записей в блоге: 1
28.08.2013, 02:25  [ТС]
Задачу вроде решил, помогите с контр примерами, чтобы уж наверняка
Если пройдет тест на контр примерах, то выложу код

Добавлено через 1 час 42 минуты
ну вроде как решил, для 30 задач ответ выдает мгновенно.
Код я еще исправлю и сделаю все аккуратно, кому не сложно посмотрите, а то может есть какие-нибудь ошибки, о которых мне следует знать
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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
#include <stdio.h>
#include <stdlib.h>
#include <locale.h>
 
#define NUMBER_PROBLEMS 30
#define NUMBER_PROCESSORS 3
 
#define min(a,b) (a)<(b)?(a):(b)
#define max(a,b) (a)>(b)?(a):(b)
 
typedef struct {
  int s;  //Свободно
  int z;  //Занято
} processor;
 
processor pr[NUMBER_PROCESSORS];
int formS[NUMBER_PROBLEMS];  //Формируемый вектор разбиений
int bestS[NUMBER_PROBLEMS];  //Лучший вектор
int bestTime = -1;           //Лучшее время
int allTime  = -1;  //Общее время выполнения всех задач на 1 процессоре
int svobTime = -1;  //Свободное время на процессор
int vloj = -1;  //Вложенность рекурсии
int Z[NUMBER_PROBLEMS] = {8, 4, 3, 2, 1, 5, 8, 9, 4, 4, 2, 7, 6, 1, 15, 10, 53, 2, 1, 10, 3, 2, 5, 3, 16, 13, 6, 7, 15, 15}; //Время выполнения заданий
int flag = -1;  //Найдено решение или нет
 
//Функции
void qSort(int *, int, int);    //Быстрая сортировка(по убыванию)
int summ(int *, int);           //Суммирование элементов массива
int work();                     //
int maxVect(int *, int);        //Возвращает максимальный элемент массива
void start();                   //распределяет время выполнения задач по процессорам
 
int main()
{
  setlocale(LC_ALL, "");
  for(int i=0; i<NUMBER_PROBLEMS; i++)
    formS[i]=bestS[i] = -1;
 
  allTime = summ(Z, NUMBER_PROBLEMS);
  svobTime = allTime / 3;
  (allTime % 3 > 0) ? (svobTime++):(svobTime);
  if(maxVect(Z, NUMBER_PROBLEMS) > svobTime) svobTime = maxVect(Z, NUMBER_PROBLEMS);
  qSort(Z, 0, NUMBER_PROBLEMS-1);
  //Вывод отсортированного массива
  for(int i=0; i<NUMBER_PROBLEMS; i++)
    printf("%4d", Z[i]);
  printf("<<<\n");
 
  //Пока не будет найдено решение
  while(work())
    svobTime += 1;
 
  //Выводим лучшее время
  printf("Best Time = %d\n", bestTime);
 
  fflush(stdin);
  getchar();
  return 0;
}
//Определения------------------------------------------------
//Общая
int work()
{
  flag = -1;
 
  razb(0, 0);
  if(flag == 1) return 0;
  return 1;
}
 
//Сумма элементов вектора
int summ(int *array, int size)
{
  int res = 0;
  for(int i=0; i<size; i++)
    res += array[i];
  return res;
}
 
//Макс вектора
int maxVect(int *array, int size)
{
  int max = array[0];
  for(int i=1; i<size; i++)
    if(max < array[i]) max = array[i];
  return max;
}
//Быстрая сортировка
void qSort(int *array, int left, int right)
{
  int x = array[(left+right) / 2],
      size = right;
  do {
    while(array[left] > x) left++;
    while(array[right] < x) right--;
 
    if(left <= right) {
      int tmp = array[left];
      array[left] = array[right];
      array[right] = tmp;
      left++; right--;
    }
  } while(left <= right);
 
  if(right > 0) qSort(array, 0, right);
  if(left < size) qSort(array, left, size);
}
 
//Проверка
int check(int number)
{
  for(int i=0; i<number; i++)
    if(pr[i].s < 0) return 1;
  return 0;
}
 
//Добавление задач в процессор
void start()
{
  for(int i=0; i<NUMBER_PROCESSORS; i++) {
    pr[i].s = svobTime;
    pr[i].z = 0;
  }
 
  int i = 0;
  while(i <= vloj)
  {
    if(formS[i]>-1 && formS[i] < 4){
        pr[formS[i]-1].s -=Z[i];
        pr[formS[i]-1].z +=Z[i];
    }
    i++;
  }
}
 
//Все разбиения
void razb(int i, int p)
{
  vloj = i;
  int b = (NUMBER_PROBLEMS-i+1 > NUMBER_PROCESSORS-p+1) ? 1 : p+1;
 
  int minn = min(p+1, NUMBER_PROCESSORS);
  for(int x=b; x<=minn; x++)
  {
    if(flag == 1) continue;
    formS[i] = x;
    for(int j=i+1;j<NUMBER_PROBLEMS;j++)
        formS[j]=-1;
 
    start();                          //
    if(check(NUMBER_PROCESSORS)){     //
      continue;                       //
    }                                 //
 
    if(i == NUMBER_PROBLEMS-1)
    {
      for(int i=0; i<NUMBER_PROBLEMS; i++)
        printf("%4d", formS[i]);
      printf("\n");
      start();
      if(max(pr[0].z, max(pr[1].z, pr[2].z)) < bestTime) bestTime = max(pr[0].z, max(pr[1].z, pr[2].z));
      for(int i=0; i<NUMBER_PROBLEMS; i++) {
        bestS[i] = formS[i];
        formS[i] = -1;
      }
      flag = 1;
    }
    else
    {
      razb(i+1, max(x, p));
    }
  }
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
28.08.2013, 02:25
Помогаю со студенческими работами здесь

Разработать программу для сохранения списка покупателей бытовой техники в виде файла
#8 с файлами у меня проблемы, а написать нужно. Помогите, пожалуйста. Правила Форума: Перепечатывайте задание на форум ...

Разработать иерархию не менее 2 классов, и программу Разработать программу для реализации игры пятнашки. Разработать 2-3
Составить описание класса многочленов от одной переменной, задаваемых степенью многочлена и массивом коэффициентов. Предусмотреть методы...

Разработать приложение для генерации (проверки) заданий типа А13
Подскажите, как решить это задание? Наиболее интересует используемая таблица. Разработать приложение в среде VBA (или Lasarus) для...

Направьте, пожалуйста, в правильном направлении
На данный момент в Java я нахожусь только на начальном уровне, до Java EE ещё не добрался. Конечная цель создание сайта с использованием...

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


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

Или воспользуйтесь поиском по форуму:
26
Ответ Создать тему
Новые блоги и статьи
Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT
bedvit 28.01.2026
Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .
Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL_LoadPNG (без SDL3_image)
8Observer8 28.01.2026
Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .
Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL3_image
8Observer8 27.01.2026
Содержание блога SDL3_image - это библиотека для загрузки и работы с изображениями. Эта пошаговая инструкция покажет, как загрузить и вывести на экран смартфона картинку с альфа-каналом, то есть с. . .
Влияние грибов на сукцессию
anaschu 26.01.2026
Бифуркационные изменения массы гриба происходят тогда, когда мы уменьшаем массу компоста в 10 раз, а скорость прироста биомассы уменьшаем в три раза. Скорость прироста биомассы может уменьшаться за. . .
Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android
8Observer8 26.01.2026
Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .
Установка Android SDK, NDK, JDK, CMake и т.д.
8Observer8 25.01.2026
Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .
Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf
8Observer8 25.01.2026
Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .
Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly
8Observer8 24.01.2026
Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru