Глава 17. Метод исчерпывающего перебора. : Программирование для всех. Языки программирования, программирование баз данных, технологии. Статьи для програмиста скачать бесплатно учебники книги документация форум : Статьи

Глава 17
Метод исчерпывающего перебора

Нахождение формул вида а ? b ? с = d
Нахождение формул вида а ? (b ? (с ? (d ? (e ? f)))) с заданным значением
Нахождение формул вида а₁ ? а₂ ? a₃ ? ••• ? a_n=b
Упражнения

Рассмотрим следующую задачу. Пусть задаются значения переменных целого типа а, b, с, d. В формуле вида а ? b ? с требуется вместо знака вопроса поставить операцию (сложение, вычитание, умножение, остаток от деления) так, чтобы значение всей формулы равнялось значению переменной d. Данную задачу можно решать методом, который получил название метода исчерпывающего перебора. Будем перебирать возможные комбинации знаков . (шестнадцать вариантов), вычислять значение формулы при каждой комбинации и отбирать формулы, удовлетворяющие условию.

Нахождение формул вида а ? b ? с = d

Напишем программу, которая для формулы вида а ? b ? с расставляет знаки операций таким образом, что значение формулы равно заданному значению d.

Рис 17.1. Поиск комбинаций знаков

Для формирования формулы будем использовать переменную s. Сначала с помощью переменной si запоминается подформула вида а ? Ь, затем подбираются знаки для второй операции. Если значение формулы совпадает с заданным значением, то формула запоминается в переменной sres. После анализа всех вариантов в текстовое поле формы выводятся либо найденные формулы, либо сообщение о том, что требуемые формулы не обнаружены. После того как формула сформирована, вычисляется ее значение с помощью стандартного метода evai. Результат работы функции на одном из тестовых примеров приведен на рис. 17.1.

Сценарий с описанной функцией имеет вид, представленный в листинге 17.1.

Листинг 17.1. Исчерпывающий Перебор. Нахождение формул вида а ? to ? с = d :

<HTML>

<HEAD>

<TITLE>Исчерпывающий перебор. Нахождение формул вида a?b?c=d</TITLE>

<!-— //

function formula(obj)

{ var a=obj.datal.value

var b=obj.data2.value

var c=obj.data3.value

var d=obj.data4.value

var sres=""

var s

var s1

var s2

var r

var p=false

for (var 1=1; i<=4; i++)

{ sl= a switch (i)

{ case 1: s1+="+"; break

case 2: s1+="-"; break

case 3: s1+="*"; break

case 4: s1+="%"; break

}

s1+=b

for (var j=l; j<=4; j++)

{ s2=""

switch (j)

{ case 1: s2+="+"; break

case 2: s2+="-"; break

case 3: s2+="*"; break

case 4: s2+="%"; break

}

s2+=c

s=sl+s2

r=eval(s)

if (r==d)

{sres +=s+ "="+d+"rn"; p=true}

}

if (p)

obj.result.value=sres

else

obj.result.value="Формулы, удовлетворяющие условию, не найдены"

}

//-—>

</script>

</HEAD>

<BODY>

<Н4>Нахождение формул вида <I>a</I>?<I>b</I>?<I>c</I>=<I>d</I></H4>

<pre>

a: <input type="text" size=20 name="data1" >

b: <input type="text" size=20 name="data2" >

c: <input type="text" size=20 name="data3" >

d: <input type="text" size=20 name="data4" >

Найденные формулы:

</pre>

<HR>

</FORM>

</BODY>

</HTML>

Нахождение формул вида а ? (b ? (с ? (d ? (e ? f)))) с заданным значением с заданным значением

На одной из Олимпиад по программированию была предложена следующая задача. Рассматривается формула вида 1 ? (2 ? (3 ? (4 ? (5 ? 6)))). Вместо знака вопроса поставьте одну из арифметических операций так, чтобы результат вычислений был равен 25. Сколько формул удовлетворяет этому условию? Сформулируем задачу в общем виде.

Необходимо написать функцию, которая для формулы вида а ? (b ? (с ? (d ? (е ? f)))) находит все комбинации знаков, при которых формула имеет заданное значение.

При решении задачи формулы будем хранить в одномерном массиве. Некоторые значения массива нам известны (заданные операнды и скобки), а некоторым элементам следует присвоить значения операций. При задании массива s все операции совпадали с операцией + (сложение). В формуле, представленной массивом, операции являются элементами с индексами 1, 4, 7, 10, 13. Для задания операций используются циклы. Когда очередная комбинация знаков готова, массив преобразуется в строку. При этом применяется метод eval для вычисления значения формулы, представленной строкой. Формулы, удовлетворяющие условию, запоминаются в строке sres. Описанная функция представлена в листинге 17.2.

Листинг 17.2. Нахождение формул вида а ? (b ? (с ? (d ? (е ? f )))) с заданным значением

<HTML>

<HEAD>

<TITLE>Нахождение формул вида а? (Ь? (с? (d? (e?f)-) ) ) </TITLE>

<!—- //

function formula (obj)

{ var a=Number(obj.datal.value)

var b=Number(obj.data2.value)

var c=Number(obj.data3.value)

var d=Number(obj.data4.value)

var e=Number(obj.dataS.value)

var f=Number(obj.data6.value)

var g=Number(obj.data7.value)

var s=new Array

(a, " + ", " (",b, "+", " (",c, " + ", " (",d, " + ", " (",e, "+", f, ") ", ") ", ") ", ") ")

var op=new Array ("+","-","*","%")

var str=""

var sres=""

var str

var p=false

for (var i=0; i<=3; i++)

{ s[1]=op[i];

for (var j=0; j<=3; j++)

{ s[4]=op[j];

for (var k=0; k<=3; k++)

{ s[7]=op[k];

for (var m=0; m<=3; m++)

{ s[10]=op[m];

for (var n=0; n<=3; n++)

{ s[13]=op[n] str=""

for (var t=0; t <= s.length-1; t++)

{ str+=s[t] };

r=eval(str)

if (r==g)

{sres +=str+ "="+g+"rn"; p=true}

}

if (P)

obj.result.value=sres

else

obj.result.value="Формул, удовлетворяющих условию, не найдено.

}

//-—>

</script>

</HEAD>

<Н4>Нахождение формул "вида a?(b?(с?(d?(e?f))))</H4>

<pre>

a: <INPUT type="text" size=20 name="datal" >

b: <INPUT type="text" size=20 name="data2" >

c: <INPUT type="text" size=20 name="data3" >

d: <INPUT type="text" size=20 name="data4" >

e: <INPUT type="text" size=20 name="data5" >

f: <INPUT type="text" size=20 name="data6" >

g: <INPUT type="text" size=20 name="data7" >

Найденные формулы:

</pre>

<HR>

</FORM>

</BODY>

</HTML>

Результат работы функции на одном из тестовых примеров приведен на рис. 17.2.

Рис 17.2. Полный перебор

При решении задачи методом исчерпывающего перебора следует обратить внимание на два момента:

1. Требуется определить порядок, в котором следует рассматривать варианты.

2. Необходимо убедиться в том, что все варианты рассмотрены. Более подробно на этих вопросах остановимся при решении следующей задачи.

Нахождение формул вида а₁ ? а₂ ? a₃ ? ... ? a_n=b

Пусть имеется п (п= < 10) целых значений а₁ ,а₂, ... а_n и целое число В. Требуется написать программу, определяющую все формулы, для которых верно

а₁ + а₂ + ... + а_n= B

где + - обозначение операции + (сложение) или - (вычитание). Например, если значение п равно 4, все числа а₁ равны 1, значение В равно 2, то в результате выполнения программы должны быть выведены следующие формулы:

1-1+1+1.= 2

1+1-1+1 = 2

1+1+1-1 = 2

Если же значение В равно 4, то в качестве ответа должна быть формула

1+1+1+1 = 4

В случае, когда В равно 5, следует выдать информацию, что требуемые формулы не найдены.

Если формула содержит n значений, то в искомой формуле должно быть использовано n знаков операций. Так как по условию задачи разрешено использовать только знаки + (плюс) или - (минус), то возможно 2"-1 различных комбинаций знаков. Например, если исследуется формула, содержащая четыре переменных вида а1 + а2 + а3 + а4, то необходимо рассмотреть и вычислить восемь формул, представленных в табл. 17.1.

Таблица 17.1. Формулы и соответствующие им комбинации знаков

№ варианта	Формула	Комбинация знаков
1	а₁ - а₂ - а₃ - а₄	- - -
2	а₁ - а₂ - а₃ + а₄	- - +
3	а₁ - а₂ + а₃ - а₄	- + -
4	а₁ - а₂ + а₃ + а₄	- + +
5	а₁ + а₂ - а₃ - а₄	+ - -
6	а₁ + а₂ - а₃ + а₄	+ - +
7	а₁ + а₂ + а₃ - а₄	+ + -
8	а₁ + а₂ + а₃ + а₄	+ + +

Если знаку - (минус) сопоставить ноль, а знаку + (плюс) — единицу, то комбинацию знаков можно трактовать как двоичную запись числа а, где 0 =< а =< 2^n-1 - 1. Разбор всех возможных комбинаций знаков соответствует анализу двоичных представлений всех чисел а, где 0 =< а =< 2^n-1 -1. Если п равно 4, то выписанные ранее комбинации знаков отвечают двоичным представлениям чисел от 0 до 7. Комбинации знаков представлены в табл. 17.2.

Таблица 17.2, Соответствие между комбинацией знаков и двоичным числом

№ варианта	Число в двоичной системе счисления	Комбинация знаков
1	000	- - -
2	001	- - +
3	010	- + -
4	011	- + +
5	100	+ - -
6	101	+ - +
7	110	+ + -
8	111	+ + +

Теперь надо уточнить порядок рассмотрения вариантов. Самый простой подход состоит в том, чтобы переход от одной комбинации к другой означал переход от двоичной записи числа а к двоичной записи числа а + 1, т. е. прибавление к текущему значению двоичного числа единицы. Если в качестве начальной комбинации знаков взять комбинацию из всех минусов (комбинация соответствует числу ноль), то после выполнения 2^n-1 -1 числа сложений будет получена комбинация знаков, состоящая только из знаков плюс, и соответствующая двоичной записи числа 2^n-1 -1. Bee возможные комбинации знаков будут исчерпаны. Таким образом, процедура моделирует увеличение двоичного числа на единицу и состоит в просмотре массива z с конца и поиске первого знака минус. При этом все встретившиеся знаки плюс заменяются знаком минус. Первый с конца знак минус также заменяется знаком плюс и просмотр массива знаков завершается. При решении задачи нам потребуется формировать массив из п - 1 знаков. Переход к следующей комбинации знаков осуществляется при вызове функции NewSign:

function NewSign{)

{ var i=n-2

while (i>=0)

{ if (z[i]=="+")

{ z[i] = "-"; i— }

else

{ z[i] = "+"; break }

}

При выполнении функции formula перебираются все комбинации знаков. Если значение формулы совпадает с требуемым значением, то такая формула запоминается. Кроме того, подсчитывается количество формул, удовлетворяющих условию. Массив, содержащий значения операндов формулы, хранится в отдельном файле. Пример работы сценария для некоторого тестового набора приведен на рис. 17.3.

Рис 17.3. Формула из n значений без скобок

Полностью сценарий с описанными функциями представлен в листинге 17.3.

Листинг 17.3. Нахождение формул вида а₁ ? а₂ ? a₃ ? ... ? a_n=b

<HTML>

<HEAD>

<TITLE>формулы вида а1 ? а2 ? а3 ? ... ? an = b</TITLE>

</script>

<!—- //

var sres=""

var k // Число комбинаций знаков

var b // Значение формулы

var n= v.length // Реальное число переменных

var varsh=0 // Количество найденных решений

// Функция Vform вычисляет значение формулы

// при заданной комбинации знаков

function Vform()

{ var s = Number (v[0])

for (var i = 0; i <= n-2; i++)

switch (z[i])

{ case "+": s += Number) v[i+l]); break

case "-": s -= Number( v[i+l]); break }

return s

}

// Функция WriteForm выводит формулу

function WriteForm()

{ var str= v[0]

for ( var i = 0 ; i <= n-2; i++)

switch ( z[i] )

{ case "+": str +="+"+ v[i+l]; break

case "-": str +="-"+ v[i+l]; break

}

str += "="+b+"rn"

return str

}

// Функция NewSign формирует следующую комбинацию знаков

function NewSign()

{ var i=n-2

while (i>=0)

{ if (z [i]=="+")

{ z[i] = "-"; i— }

else

{ z[i] = "+"; break }

}

// Функция InitSign формирует начальную комбинацию знаков

function InitSign()

{ for (var i =0; i<= n-2; i++)

{ z[i] = "-" }

}

// Функция formula просматривает все варианты и отбирает

// удовлетворяющие условию

function formula (obj)

( b= obj.valform.value

if (b=="")

alert("Вы не ввели значение формулы")

else

{ k = Math.pow(2,n-l)

sres=""

varsh=0

InitSign()

for (var t = 1; t<= k; t++)

{ if (VformO ==Number(b))

{ sres += WriteForm(); varsh++ }

NewSign()

}

if (varsh==0)

sres= "таких формул нет"

obj.result.value=sres

obj.datal.value=varsh

}

function writearr(obj)

{obj.vararray.value=v}

//-—>

</script>

</HEAD>

<Н4>Формулы вида al?a2?a3?...?an=b</H4>

<pre>

Значения элементов: <input type="text" size=20 name="vararray">

Значение формулы: <input type="text" size=20 name="valform"><BR>

Количество формул: <input type="text" size=20 name="datal">

Найденные формулы:

</pre>

</FORM>

</BODY>

</HTML>

Упражнения

1. Напишите функцию, которая для формулы вида ((а ? b) ? с) ? ((d ? e) ? f), где вместо знака вопроса может стоять любая из операций сложения, вычитания, умножения, находит все комбинации знаков, при которых формула имеет заданное значение.

2. Напишите сценарий, который размещает цифры 1, 2, 3, 4, 5, 6, 7, 8, 9 так, чтобы имело место: ------/------=n, где n равно одному из чисел 2, 3, 4, 5, 6, 7, 8, 9.

3. Пусть задана формула вида А1 + A2 + ... + An, где Аi, может принимать целое значение, знак + соответствует операции сложения, вычитания или умножения. Напишите сценарий, который определяет, существует ли набор знаков операций, при которых формула принимает заданное значение.

4. Пусть задана формула вида А1 + A2 + ... + An, где Аi может принимать целое значение, знак + соответствует операции сложения, вычитания или умножения. Напишите сценарий, который определяет все наборы знаков операций, при которых формула принимает заданное значение.

5. Пусть задана формула вида А1 + A2 + ... + An, где Аi принимает значения либо истина, либо ложь, знак + соответствует операции дизъюнкции или конъюнкции. Напишите сценарий, который определяет, существует ли набор знаков операций, при которых формула принимает заданное значение.

6. Пусть задана формула вида А1 + A2 + ... + An, где Аi может принимать значения либо истина, либо ложь, знак + соответствует операции дизъюнкции или конъюнкции. Напишите сценарий, который по указанному набору операций присваивает переменным Ai такие значения, чтобы значение всей формулы совпадало с заданным.

7. Дано уравнение вида F(x) = 0, где F(x) строится из целых чисел, арифметических операций (+, -, *, /), и переменной х, которая может входить не более одного раза. Напишите программу, которая решает заданное уравнение и печатает его корни в виде несократимой дроби.

После публикации 29 тестовых версий анонсирован первый стабильный релиз MySQL 5.1, пригодный для промышленной эксплуатации и обеспечивающий увеличение производительности для "тяжелых" SQL запросов, по сравнению с MySQL 5.0, примерно на 15-20%. Главные новшества появившиеся в MySQL 5.1:

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

Аннотация. В статье кратко рассматривается архитектура AMD64 компании AMD и ее реализация EM64T компании Intel. Описаны особенности архитектуры, ее возможности, достоинства и недостатки.