0 / 0 / 0
Регистрация: 25.03.2012
Сообщений: 15
1

Полный перебор и сокращенный перебор, путем исключения одного цикла

13.06.2012, 15:43. Показов 3687. Ответов 4
Метки нет (Все метки)

1) Разработать на основе метода полного перебора программу razmen1 для решения задачи о способах размена купюры достоинством 100 условных единиц монетами по 2, 5, и10 условных единиц. На печать вывести общее число переборов n, количество способов размена k и все способы размена.

2) На основе программы razmen1 разработать программу razmen2 сокращенного перебора путем исключения одного цикла. На печать вывести общее число переборов n, количество способов размена k и все способы размена.
__________________
Помощь в написании контрольных, курсовых и дипломных работ здесь
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
13.06.2012, 15:43
Ответы с готовыми решениями:

Полный перебор
Здравствуйте. Скорее всего, я пришел не по адресу и мне следовало бы задать свой вопрос где-нибудь...

Полный перебор
Дано множество целых чисел. Требуется разбить множество на две части суммы элементов которых равны....

Полный перебор
Добрый день. Возникла такая ситуация. Есть множество Х(други орграфа) и множество W(числа) и...

Полный перебор
Всем привет. Когда у нас есть фиксированное количество переменных и для них есть фиксированная...

4
3941 / 1866 / 337
Регистрация: 16.03.2012
Сообщений: 3,880
13.06.2012, 19:29 2
По задаче 1:
Delphi
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
//Разработать на основе метода полного перебора программу razmen1 для решения
//задачи о способах размена купюры достоинством 100 условных единиц
//монетами по 2, 5, и 10 условных единиц.
//На печать вывести общее число переборов n, количество способов размена k
//и все способы размена.
program Project1;
 
{$APPTYPE CONSOLE}
 
uses
  SysUtils;
 
Type
  //Запись мониторинга использования монеты
  MonMonet = Record
               quality : Integer;  //Достоинство монеты
               UseCount : Integer; //Количество использования
             End;
Const
  Bond = 100; //Купюра
Var
  //Массив мониторинга использования монеты
  Monets : Array[0..2] Of MonMonet = (
              (quality:2;
               UseCount:0),
              (quality:5;
               UseCount:0),
              (quality:10;
               UseCount:0));
  n : Integer = 0; //Будем считать общее количество переборов
  k : Integer = 0; //Будем считать количество способов размена
  i,Sum : Integer;
  Perenos : Boolean;
begin
  //Обработка...
 
  Repeat
    //Проверяем сумму по текущему подбору монет
    Sum:=0;
    For i:=Low(Monets) To High(Monets) Do
    Sum:=Sum+Monets[i].quality*Monets[i].UseCount;
 
    Perenos:=False;
    If Sum<Bond Then
    //Сумма монет ещё не достигл нужной...
    //Нарастим вариант подбора
    Inc(Monets[High(Monets)].UseCount) Else
    //Сумма монет превысила нужную...
    //или набрали нужную сумму...
    Begin
      If Sum=Bond Then //Набрали нужную сумму...
      Begin
        Inc(k);
        Write(k:3,': ');
        //Выдадим вариант подбора:
        For i:=Low(Monets) To High(Monets) Do
        Write(Monets[i].quality,' x ',Monets[i].UseCount:2,',  ');
        WriteLn;
      End;
 
      //Подготовим следующий вариант...
      For i:=High(Monets) DownTo Low(Monets) Do
      If Perenos Then
      Begin
        Inc(Monets[i].UseCount);
        Perenos:=False;
        Break;
      End Else
      If Monets[i].UseCount<>0 Then
      Begin
        Monets[i].UseCount:=0;
        Perenos:=True;
      End;
    End;
    Inc(n); //Считаем количество вариантов перебора
  Until Perenos; //Закончили перебор
 
  WriteLn;
  WriteLn('n = ',n);
 
  ReadLn; //Ждём ответа для выхода...
end.
Добавлено через 22 минуты
Ну как я понял 2-ю задачу, нужно сократить перебор на одну монету. Скорее всего имеется в виду - оценка, на сколько меняется количество вариантов перебора. Поэтому самый простой вариант: уменьшите массив монет, убрав любую. Этого будет достаточно:
Delphi
1
2
3
4
5
6
  //Массив мониторинга использования монеты
  Monets : Array[0..1] Of MonMonet = (
              (quality:2;
               UseCount:0),
              (quality:10;
               UseCount:0));
Либо поставить фиксированное значение количества первой монеты:
Delphi
1
2
3
4
5
6
7
8
  //Массив мониторинга использования монеты
  Monets : Array[0..2] Of MonMonet = (
              (quality:2;
               UseCount:10), //Берём 10 монет достоинством 2 у.е.
              (quality:5;
               UseCount:0),
              (quality:10;
               UseCount:0));
и строку 62 написать так:
Delphi
1
     For i:=High(Monets) DownTo Low(Monets)+1 Do
Добавлено через 59 минут
Вот ещё вариант вотрой задачи. Поскольку у нас последним выполняется перебор монет последнего достоинства, можно вместо этого перебора сразу считать, сколько монет последнего достоинства необходимо для дополнения до нужной суммы. Т.е. этот перебор можно исключить из цикла:
При этом количество вариантов размена остаётся прежним, а общее число переборов существенно сокращается.
Delphi
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
//На основе программы razmen1 разработать программу razmen2 сокращенного перебора
//путем исключения одного цикла. На печать вывести общее число переборов n,
//количество способов размена k и все способы размена.
program Project1;
 
{$APPTYPE CONSOLE}
 
uses
  SysUtils;
 
Type
  //Запись мониторинга использования монеты
  MonMonet = Record
               quality : Integer;  //Достоинство монеты
               UseCount : Integer; //Количество использования
             End;
Const
  Bond = 100; //Купюра
Var
  //Массив мониторинга использования монеты
  Monets : Array[0..2] Of MonMonet = (
              (quality:2;
               UseCount:0),
              (quality:5;
               UseCount:0),
              (quality:10;
               UseCount:0));
  n : Integer = 0; //Будем считать общее количество переборов
  k : Integer = 0; //Будем считать количество способов размена
  i,Sum : Integer;
  Perenos : Boolean;
begin
  //Обработка...
 
  Repeat
    //Проверяем сумму по текущему подбору монет
    Sum:=0;
    For i:=Low(Monets) To High(Monets)-1 Do
    Sum:=Sum+Monets[i].quality*Monets[i].UseCount;
 
    //Посчитаем, сколько нужно монет последнего достоинства
    //чтобы набрать нужную сумму
    i:=Bond-Sum;
    If i>=1 Then
    With Monets[High(Monets)] Do
    Begin
      UseCount:=i Div quality;
      If (i Mod quality)<>0 Then Inc(UseCount);
      Sum:=Sum+(quality*UseCount);
    End;
 
    Perenos:=False;
    If Sum<Bond Then
    //Сумма монет ещё не достигла нужной...
    //Нарастим вариант подбора
    Inc(Monets[High(Monets)].UseCount) Else
    //Сумма монет превысила нужную...
    //или набрали нужную сумму...
    Begin
      If Sum=Bond Then //Набрали нужную сумму...
      Begin
        Inc(k);
        Write(k:3,': ');
        //Выдадим вариант подбора:
        For i:=Low(Monets) To High(Monets) Do
        Write(Monets[i].quality,' x ',Monets[i].UseCount:2,',  ');
        WriteLn;
      End;
 
      //Подготовим следующий вариант...
      For i:=High(Monets) DownTo Low(Monets) Do
      If Perenos Then
      Begin
        Inc(Monets[i].UseCount);
        Perenos:=False;
        Break;
      End Else
      If Monets[i].UseCount<>0 Then
      Begin
        Monets[i].UseCount:=0;
        Perenos:=True;
      End;
    End;
    Inc(n); //Считаем количество вариантов перебора
  Until Perenos; //Закончили перебор
 
  WriteLn;
  WriteLn('n = ',n);
 
  ReadLn; //Ждём ответа для выхода...
end.
2
0 / 0 / 0
Регистрация: 25.03.2012
Сообщений: 15
14.06.2012, 13:53  [ТС] 3
Вот пример...
Миниатюры
Полный перебор и сокращенный перебор, путем исключения одного цикла   Полный перебор и сокращенный перебор, путем исключения одного цикла  
0
3941 / 1866 / 337
Регистрация: 16.03.2012
Сообщений: 3,880
14.06.2012, 18:29 4
Лучший ответ Сообщение было отмечено как решение

Решение

Ну, можно и так (первая задача):
Delphi
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
//Разработать на основе метода полного перебора программу razmen1 для решения
//задачи о способах размена купюры достоинством 100 условных единиц
//монетами по 2, 5, и 10 условных единиц.
//На печать вывести общее число переборов n, количество способов размена k
//и все способы размена.
program Project1;
 
{$APPTYPE CONSOLE}
 
uses
  SysUtils;
 
Const
  Bond = 100; //Купюра
  //Достоинства монет
  q1 = 2;
  q2 = 5;
  q3 = 10;
Var
  i1,i2,i3 : Integer;
  n : Integer = 0; //Будем считать общее количество переборов
  k : Integer = 0; //Будем считать количество способов размена
begin
 
  //Обработка...
  For i1:=0 To (Bond Div q1) Do
  For i2:=0 To (Bond Div q2) Do
  For i3:=0 To (Bond Div q3) Do
  If (q1*i1+q2*i2+q3*i3)=Bond Then //Набрали нужную сумму...
  Begin
    Inc(k);
    Write(k:3,': ');
    //Выдадим вариант подбора:...
    WriteLn(q1,' x ',i1:2,',  ',q2,' x ',i2:2,',  ',q3,' x ',i3:2);
    Inc(n);
  End Else Inc(n);
 
  WriteLn;
  WriteLn('n = ',n);
 
  ReadLn; //Ждём ответа для выхода...
end.
И вторая:
Delphi
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
//На основе программы razmen1 разработать программу razmen2 сокращенного перебора
//путем исключения одного цикла. На печать вывести общее число переборов n,
//количество способов размена k и все способы размена.
program Project1;
 
{$APPTYPE CONSOLE}
 
uses
  SysUtils;
 
Const
  Bond = 100; //Купюра
  //Достоинства монет
  q1 = 2;
  q2 = 5;
  q3 = 10;
Var
  i1,i2,i3 : Integer;
  n : Integer = 0; //Будем считать общее количество переборов
  k : Integer = 0; //Будем считать количество способов размена
begin
 
  //Обработка...
  For i1:=0 To (Bond Div q1) Do
  For i2:=0 To (Bond Div q2) Do
  If (q1*i1+q2*i2)<=Bond Then
  Begin
    i3:=(Bond-(q1*i1+q2*i2)) Div q3;
    If (q1*i1+q2*i2+q3*i3)=Bond Then //Набрали нужную сумму...
    Begin
      Inc(k);
      Write(k:3,': ');
      //Выдадим вариант подбора:...
      WriteLn(q1,' x ',i1:2,',  ',q2,' x ',i2:2,',  ',q3,' x ',i3:2);
    End;
    Inc(n);
  End Else Inc(n);
 
  WriteLn;
  WriteLn('n = ',n);
 
  ReadLn; //Ждём ответа для выхода...
end.
Да... облом.
2
0 / 0 / 0
Регистрация: 25.03.2012
Сообщений: 15
14.06.2012, 21:54  [ТС] 5
Спасибо !
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
14.06.2012, 21:54

задача на полный перебор
найти сумму всех трёхзначных чисел, в записи которых все цифры нечётные.

Задача на полный перебор.
Расшифровать ребус, полученный в результате замены одинаковых букв одинаковыми цифрами:...

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

Полный перебор в Excel
Нужно реализовать алгоритм полного перебора в excel на любом примере. Необходимо для тестового...


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

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

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