7. 4 задачи для самостоятельного решения

7. 4 ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ

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

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

3. Модой массива называется число M, которое встречается в массиве наиболее часто. Если в массиве имеется несколько наиболее часто встречающихся элементов и число их вхождений совпадает, то считается, что массив не имеет моды. Напишите программу, которая либо вычисляет моду массива, либо устанавливает, что последний её не имеет.

4. (*) Дано N целых чисел. Упорядочить их по неубыванию методом фон Неймана: завести два массива A и B и записать исходные числа в A; упорядочить пары соседних чисел (А₁ и А₂, A₃ и A₄ и т. д. ) и записать их в B; взять из B по две соседние упорядоченные пары и, слив их в упорядоченные четверки, снова записать в A; затем каждые две соседние четверки из B слить в упорядоченные восьмерки и перенести в A; и т. д.

5. (*) (По [Окулов, 2002, с. 270]) Напишите программу, осуществляющую поиск k-го элемента в неупорядоченном массиве следующим образом, называемым случайным поиском. Выбирается случайным образом элемент с номером q. Массив X разбивается на три части: элементы, меньшие X[q], равные X[q] и большие X[q]. А затем, в зависимости от количества элементов в каждой части, рекурсивно выбирается одна из частей для дальнейшего поиска.

6. (*) [Шень, 1995] Ещё один практически важный алгоритм сортировки таков: чтобы отсортировать массив, выберем случайный его элемент b, и разобьем массив на три части: меньшие b, равные b и большие b. Теперь осталось отсортировать первую и третью части: это делается тем же способом. Время работы этого алгоритма - случайная величина; можно доказать, что в среднем он работает не больше C*n*log n (на практике - он один из самых быстрых). Приведите его рекурсивную и нерекурсивную реализации.

7. В одномерном числовом массиве найдите максимальный элемент.

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

9. (*) Найдите количество различных чисел среди элементов данного массива. Число действий порядка n*log n.

Указание: Отсортируйте массив, а затем посчитайте количество различных элементов, просматривая элементы массива по порядку.

10. (*) [Шень, 1995] Дано n точек на плоскости. Указать (n-1)-звенную несамопересекающуюся незамкнутую ломаную, проходящую через все эти точки. Соседним отрезкам ломаной разрешается лежать на одной прямой. Число действий порядка n*log n.

Указание: Упорядочим точки по x-координате, а при равных x-координатах - по y-координате. В таком порядке и можно проводить ломаную.

ЛАБОРАТОРНАЯ РАБОТА 8. СТРОКОВЫЙ ТИП ДАННЫХ В ПРОГРАММАХ НА VBSCRIPT

8. 1 ЦЕЛЬ РАБОТЫ

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

8. 2 ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ

Для работы с символьной информацией используют структуру данных – строка. В языке VBScript нет символьного типа данных.. В VBS этот тип замещен типом String или строковым типом, то есть если мы хотим работать с отдельным символом, нам всё равно приходится работать с ним как со строкой.

Строка состоит из последовательности символов, которые являются элементами кодовой таблицы ASCII. Всего в данной таблице 256 символов, которые пронумерованы (то есть имеют код) от 0 до 255. Все символы кодовой таблицы ASCII упорядочены в соответствии с расположением в этой таблице. Например, символ «А» меньше символа «Б» и тем более меньше символа «а». Объяснение этому очень простое код символа «А» - 192, «Б» - 193, а «а» - 224. в демонстрационных примерах находится программа ASCII. vbs, которая выводит последовательно все символы данной таблицы.

Мы уже сталкивались с данными типа String при работе с функцией MsgBox (в качестве основного аргумента используется не что иное, как данные строкового типа). Попробуем кратко его описать. Этот тип индексирован, то есть можно получить доступ к любой части строки, зная номер символа с которого начинается искомая часть. На этом типе данных можно производить сравнение переменных. Каждая строка (а именно так общепринято называть переменные и константы этого типа) рассматривается в лексикографическом формате. Сначала по коду в таблице ASCII сравниваются первые их символы (так будем называть строку из одного элемента), если код первого символа первой строки больше кода первого символа второй строки то первая строка больше второй, если меньше, то соответственно наоборот. Если же первые символы по коду равны, то сравнение переходит на второй символ если и это не прояснит ситуацию, то перебираются следующие символы до конца строки. Если в первой строке окажется меньше символов чем во второй, и при этом первая строка является началом второй, то первая строка меньше второй. Строки равны тогда и только тогда, когда последовательно равны коды каждого из символов, входящих в сравниваемые строки.

Количество входящих в строку символов называется длиной строки.

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

В языке VBS объявление строк ничем не отличается от объявления любой другой переменной:

 

 

Dim str

Где dim – ключевое слово при объявлении переменных;

  str – интендификатор (имя переменной).

 

Для того чтобы чтобы «положить» в переменную str строку: «Это строка номер 1», надо воспользоваться оператором присваивания:

 

Str=”Это строка номер 1”

 

Надо отметить тот факт, что сейчас в программировании наиболее распространено именно программирование на строках. В частности, язык гипертекстовой разметки HTML, на котором построено всё Интернет-программирование оперирует только строками.

В связи с выше сказанным все современные языки программирования, в том числе и VBScript представляют развитые средства для работы со строками.

Рассмотрим некоторые из них.

Для работы со строками может потребоваться получение данных в виде строки из других типов данных. Для этого используется уже знакомая функция «CStr»(Convert to String – преобразование в строку).

 

Таблица 12 – Типы аргументов, возвращаемые функцией CStr

Тип аргумента	Что возвратит функция CStr
Boolean	Строковую константу «Истина» или «Ложь»
Date	Дату в виде дд. мм. гг (день. месяц. год)
Empty (неинициализированная переменная)	Пустая строка
Числовые форматы Long, Double…	Представление числа виде строки
Большинство других типов	Вызовут ошибку программы

 

Интересны также функции обратного преобразования. Их список можно посмотреть в первой лабораторной работе.

Чтобы избежать ошибок преобразования из строки в другой тип данных применяются функции проверки содержимого строки:

IsDate возвращает значение «Истина», если строка представима виде даты, и «Ложь» в противном случае.

IsNumeric возвращает значение «Истина», если строка представима виде числа и «Ложь» в противном случае.

 

Теперь же рассмотрим различные функции работы со строками:

Таблица 13 - Функции работы со строками

Название функции	Описание работы функции	Тип аргумента	Тип функции
Mid(str, start[, len])	Возвращает подстроку строки str, начиная с позиции start длиной len. Если len не указан возвращаются все символы начиная со start	Str: string Start, len: Integer	String
Len(str)	Возвращает длину строки str	Str: string	Integer
Str1+Str2	Возвращает конкатенацию str1 и str2 Рекомендуется к использованию только, если Вы уверены, что Str1и Str2 типа string	Str1, Str2: string	String
Str1& Str2	Возвращает конкатенацию str1 и str2	Str1, Str2: string	String
InStr([start, ] source, pattern)	Возвращает индекс символа, начиная с которого pattern входит в source. Если указан параметр start, поиск начинается с него. Поиск идет слева направо. Если source=””, то InStr-0 Если pattern=””, то InStr-start Если pattern не найден в source, то InStr-0 Если start> len(pattern), то InStr – 0????	Start: integer Source: string pattern: string	Integer
InStrRev(source, pattern[, start])	То же, что InStr, но поиск происходит справа налево с позиции start.	Start: integer Source: string pattern: string	Integer

 

Рассмотрим другие функции необходимые для работы со строками:

⇐ Предыдущая20212223242526272829Следующая ⇒

Поделиться:

Воспользуйтесь поиском по сайту: