НазадСодержаниеВперед

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

Рассмотрим следующую задачу. Пусть задаются значения переменных целого типа а, 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> 

<script LANGUAG="JavaScript"> 

<!-— //

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+"\r\n"; 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> 

<FORM name="forml"> 

<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" > 

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

<textarea cols=30 rows=5 name="result" ></textarea> 

</pre>

<HR>

<input type="button" value=0npeделить onClick="formula(forml)"> 

<input type="reset" value=Отменить> 

</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> 

<script language="JavaScript"> 

<!—- //

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+"\r\n"; p=true} 

} 

} 

} 

} 

} 

if (P)

obj.result.value=sres 

else

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

}

//-—> 

</script> 

</HEAD> 

<BODY bgcolor=silver>

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

<FORM name="form1"> 

<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" > 

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

<textarea cols=30 rows=5 name="result" > </textarea> 

</pre> 

<HR> 

<INPUT type="button" value=0npeделить onClick="formula(forml)">

<INPUT type="reset" value=0тменить> 

</FORM>

</BODY> 

</HTML>

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

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

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

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

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

  Нахождение формул вида а 1 ? а 2 ? a 3 ? ... ? a n =b

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

а 1 + а 2 + ... + а n = B

где + - обозначение операции + (сложение) или - (вычитание). Например, если значение п равно 4, все числа а 1   равны 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

а 1 - а 2 - а 3 - а 4

- - -

2

а 1 - а 2 - а 3 + а 4

- - +

3

а 1 - а 2 + а 3 - а 4

- + -

4

а 1 - а 2 + а 3 + а 4

- + +

5

а 1 + а 2 - а 3 - а 4

+ - - 

6

а 1 + а 2 - а 3 + а 4

+ - +

7

а 1 + а 2 + а 3 - а 4

+ + -

8

а 1 + а 2 + а 3 + а 4

+ + +

Если знаку - (минус) сопоставить ноль, а знаку + (плюс) — единицу, то комбинацию знаков можно трактовать как двоичную запись числа а, где 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. Нахождение формул вида а 1 ? а 2 ? a 3 ? ... ? a n =b

<HTML> 

<HEAD>

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

<script src="arrform.js">

</script>

<script language="JavaScript">

<!—- //

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+"\r\n" 

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> 

<BODY bgcolor=silver>

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

<FORM name="form1"> 

<pre>

<input type="button" value=MaccnB onClick="writearr(form1)"> 

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

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

<input type="button" value=0пpeдeлить onClick="formula(forml)"> 

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

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

<textarea cols=30 rows=3 name="result" > </textarea> 

</pre> 

<input type="reset" value=Отменить onClick= 'sres=""; varsh=0 '>

</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) строится из целых чисел, арифметических операций (+, -, *, /), и переменной х, которая может входить не более одного раза. Напишите программу, которая решает заданное уравнение и печатает его корни в виде несократимой дроби.

НазадСодержаниеВперед
Сайт создан в системе uCoz