2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу 1, 2  След.
 
 Помогите понять смысл задания
Сообщение01.03.2010, 11:05 
Привет всем.

Я новичок. У меня сомнения... Вопрос может оказаться тупым :P

Мне на VB такое задание надо сделать:
Ввести упорядоченный массив q = {1.5, 2, 3.1, 4.2, 6, 7.5, 8.3, 9}.
Удалить из массива элемент с задаваемым индексом k, а затем вставить элемент с вводимым значением s так, чтобы не нарушилась упорядоченность.
Вывести полученный массив.



Вопрос по "а затем вставить элемент с вводимым значением s так, чтобы не нарушилась упорядоченность."

Надо к старому массиву добавить новый элемент, а потом отсортировать по возрастанию или надо сравнивать по порядку новый элемент(тот, что со значением s) с элементами массива, пока s не окажется чуть больше значения элемента слева, а потом как-то поменять индексы массива(передвинуть значения и присвоить индексы = их индекс + 1), которые будут правее...???

Чтоб было более понятнее, напишу так:
y(0)=1
y(1)=2
y(2)=3
y(3)=4
y(4)=5

Надо вставить новый элемент со значением s в массив. Допустим, s=3,14. Тогда как получить это? :
y(0)=1
y(1)=2
y(2)=3
y(3)=3.14
y(4)=4
y(5)=5


Сделать то я могу(способом отмеченным зелёным текстом), но не будет ли это противоречить тексту самого задания??

 
 
 
 Re: Помогите понять смысл задания
Сообщение01.03.2010, 12:14 
Аватара пользователя
Оба способа, которые Вы описали, допустимые, в том смысле, что решают задачу. В задании не сказано, как конкретно должен быть реализован алгоритм. Описано только, что он должен делать. Это значит, что Вы можете выбирать ту реализацию, которая Вам больше нравится.

 
 
 
 Re: Помогите понять смысл задания
Сообщение01.03.2010, 12:19 
Раз массив уже упорядочен, то зачем сортировать? Это накладно.
В чем конкретно сложности при не зеленом подходе?

 
 
 
 Re: Помогите понять смысл задания
Сообщение01.03.2010, 14:15 
p51x в сообщении #293541 писал(а):
Раз массив уже упорядочен, то зачем сортировать? Это накладно.

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

 
 
 
 Re: Помогите понять смысл задания
Сообщение01.03.2010, 14:43 
Спасибо большое.

ewert в сообщении #293568 писал(а):
Дописать новый элемент в конец, а потом потихоньку опускать к началу (собственно, к этому сортировка и сведётся).


А покажите пример откуда-нибудь пожалуйста, а то я забыл как это делать(
боюсь сделать не правильно.

 
 
 
 Re: Помогите понять смысл задания
Сообщение01.03.2010, 15:20 
Mikle1990 в сообщении #293580 писал(а):
боюсь сделать не правильно
А Вы не бойтесь. Сделайте и напишите сюда решение, а мы проверим.

ewert в сообщении #293568 писал(а):
p51x в сообщении #293541 писал(а):
Раз массив уже упорядочен, то зачем сортировать? Это накладно.

Практически нет. Дописать новый элемент в конец, а потом потихоньку опускать к началу (собственно, к этому сортировка и сведётся).
Все-таки немного накладно: при пузырьковой сортировке сравнений будет столько же, сколько и при прямой вставке, а присваиваний -- в два раза больше. Хотя, конечно, в данном случае ...

 
 
 
 Re: Помогите понять смысл задания
Сообщение01.03.2010, 19:43 
А вот и решение :D
Если кто не в курсе: язык-VB, задание смотрите в первом посте темы)

Код:
Public Class Form7

    'процедура ввода элемантов массива
    Sub vvodMas(ByRef y() As Single, ByVal n As Integer)
        Dim i As Integer

        For i = 0 To n - 1
            y(i) = Val(InputBox("Введите значение y(" & i & "):", _
                         "Ввод значений элементов массива Y"))

        Next
    End Sub

    'процедура вывода элемантов массива
    Sub vivodMas(ByVal f() As Single, ByVal n As Integer, ByVal T As ListBox)
        Dim i As Integer
        Dim st As String = ""

        For i = 0 To n - 1
            st = st + Format(f(i), "00.00") + Space(4)
        Next
        T.Items.Add(st)
    End Sub

    'процедура выполняющая удаление элемента с индекосм "k"
    Sub udalk(ByVal lom() As Single, ByRef z() As Single, ByVal n As Integer, ByVal k As Integer)
        Dim i As Integer
        Dim j As Integer
        j = 0

        For i = 0 To n - 1
            If i <> k Then
                z(j) = lom(i)
                j = j + 1
            End If
        Next
    End Sub

    'процедура выполняющая вставку нового элемента со значением "s" в массив
    Sub vstavs(ByRef zbk() As Single, ByVal n As Integer, ByVal newz As Single)
        zbk(n - 1) = newz
    End Sub

    'процедура сортировки массива по возратстанию
    Sub sort(ByRef mis() As Single, ByVal n As Integer)
        Dim Tmp As Single
        Dim i As Integer
        Dim j As Integer

        For i = 0 To n - 1
            For j = 0 To n - 2
                If mis(j) > mis(j + 1) Then
                    Tmp = mis(j)
                    mis(j) = mis(j + 1)
                    mis(j + 1) = Tmp
                End If
            Next j
        Next i

    End Sub


    Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click
        Dim k As Integer 'к - индекс эемента, которого нужно удалить
        Dim n As Integer 'n - кол-во элементов в массиве
        Dim s As Single  's - значение эемента, которого нужно добавить
        n = CInt(TextBox1.Text)
        Dim y(0 To n - 1) As Single
        Dim z(0 To n - 1) As Single

        k = CInt(TextBox2_1.Text)
        s = CSng(TextBox2_2.Text)

        vvodMas(y, n)         ' ввод массива
        vivodMas(y, n, L_B_1) ' вывод массива на экран
        udalk(y, z, n, k)     ' удаление элемента с индексом "k"
        vstavs(z, n, s)       ' вставка нового элемента в массив со значением "s"
        sort(z, n)            ' сортировка массива по возрастанию
        vivodMas(z, n, L_B_2) ' вывод массива на экран
    End Sub

    Private Sub Button5_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button5.Click
        Close()
        Form0.Show()
    End Sub

End Class

 
 
 
 Re: Помогите понять смысл задания
Сообщение01.03.2010, 21:50 
Да вроде бы нормально, только это решение не совсем той задачи, которая сформулирована в первом посте темы. У Вас в задании сказано:
Mikle1990 в сообщении #293522 писал(а):
Ввести упорядоченный массив
Поэтому, на мой взгляд, при вводе массива надо проверять его элементы на возрастание и при нарушении этого условия выдавать сообщение и больше ничего не делать. Кроме этого, неполохо бы проверять при вводе корректность формата вводимых элементов.

При вводе индекса удаляемого элемента надо бы проверить, что он находится в заданном диапазоне ([0, n-1]). При удалении элемента нет никакой необходимости строить новый массив: вполне можно можно просто сдвинуть влево все элементы исходного массива, начиная с индекса k+1.

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

Ну и наконец, если уж Вы сортируете произвольный массив, то имеет смысл выходить из внешнего цикла, если во внутреннем не было обнаружено ни одной инверсии.

 
 
 
 Re: Помогите понять смысл задания
Сообщение01.03.2010, 22:10 
Maslov в сообщении #293591 писал(а):
Все-таки немного накладно: при пузырьковой сортировке сравнений будет столько же, сколько и при прямой вставке, а присваиваний -- в два раза больше. Хотя, конечно, в данном случае ...

Ну, может, в пару-другую раз и больше (не считал). Но уж точно не на порядок и даже не на долю порядка. Зато логически -- явно проще.

(я воспринял слова "Удалить из массива элемент с задаваемым индексом k, а затем вставить элемент с вводимым значением s так, чтобы" как две независимых операции; тогда мой вариант -- почти вне конкуренции. Если же обе операции предполагаются одновременными, то да -- тот вариант не вполне идеален; но всё равно: по порядку -- он такой же, логически же -- проще.)

 
 
 
 Re: Помогите понять смысл задания
Сообщение01.03.2010, 22:21 
ewert, конечно, Вы правы: в данном случае чем проще, тем лучше. Это я так, к словам чепляюсь.

 
 
 
 Re: Помогите понять смысл задания
Сообщение01.03.2010, 22:30 

(Оффтоп)

Maslov в сообщении #293735 писал(а):
ewert, конечно, Вы правы: в данном случае чем проще, тем лучше. Это я так, к словам чепляюсь.

так и я ровно так же: тихо занудствую

 
 
 
 Re: Помогите понять смысл задания
Сообщение02.03.2010, 10:27 
Maslov в сообщении #293728 писал(а):
При пузырьковой сортировке массива, у которого только последний элемент, возможно, находится не на своем месте, достаточно только внутреннего цикла (внешний не нужен), только выполнять его надо от больших значений индекса к меньшим.

Ну и наконец, если уж Вы сортируете произвольный массив, то имеет смысл выходить из внешнего цикла, если во внутреннем не было обнаружено ни одной инверсии.


Я цитирую этот участок текста, так как то, что у Вас написано до - это нужно, но не у нас.... у нас вообще информатика тугая. Делаем программы, которые только в рамках задания могу работать. :?

А теперь о самом деле. Добавленный элемент в массиве - всегда "у нас" будет в конце, поэтому я сделал так:
Код:
    'процедура сортировки массива по возратстанию
    '(учитывая, что весь массив, кроме последнего элемента, уже отсортирован)
    Sub sort(ByRef mis() As Single, ByVal n As Integer)
        Dim Tmp As Single
        Dim j As Integer

        For j = n - 1 To 1 Step -1
            If mis(j) < mis(j - 1) Then
                Tmp = mis(j)
                mis(j) = mis(j - 1)
                mis(j - 1) = Tmp
            Else
                Exit For
            End If
        Next
    End Sub



Ну это ещё не конец) Я решил закончить эту лабу после:
Maslov в сообщении #293728 писал(а):
При удалении элемента нет никакой необходимости строить новый массив: вполне можно можно просто сдвинуть влево все элементы исходного массива, начиная с индекса k+1.

Я сделал вот так:
Код:
    'процедура выполняющая удаление элемента с индекосм "k"
    Sub delka(ByRef lom() As Single, ByVal n As Integer, ByVal k As Integer)
        Dim i As Integer
        For i = k To n - 2
            lom(i) = lom(i + 1)
        Next
    End Sub



Проверьте пожалуйста эти 2 мои процедуры :)

 
 
 
 Re: Помогите понять смысл задания
Сообщение02.03.2010, 10:44 
Во-первых, у Вас верхние границы циклов почему-то занижены на единицу (так, как если бы длина списка была (n-1), а не n). Во-вторых, в первой процедуре одно присвоение внутри цикла явно лишнее (ведь одно-то из переставляемых значений фиксировано). Достаточно так:
Код:
        Tmp = mis(n)
        For j = n To 1 Step -1
            If mis(j) < mis(j - 1) Then
                mis(j) = mis(j - 1)
                mis(j - 1) = Tmp
            Else
                Exit For
            End If
        Next

И даже ещё лучше так:
Код:
        Tmp = mis(n)
        For j = n To 1 Step -1
            If Tmp < mis(j - 1) Then
                mis(j) = mis(j - 1)
                mis(j - 1) = Tmp
            Else
                Exit For
            End If
        Next

 
 
 
 Re: Помогите понять смысл задания
Сообщение02.03.2010, 11:35 
ewert в сообщении #293807 писал(а):
Во-первых, у Вас верхние границы циклов почему-то занижены на единицу (так, как если бы длина списка была (n-1), а не n).
С индексами всё нормально, просто они с 0 начинаются, а не с 1.
Поэтому всё-таки:
Код:
        Tmp = mis(n)
        For j = n-1 To 1 Step -1
            If Tmp < mis(j - 1) Then
                mis(j) = mis(j - 1)
                mis(j - 1) = Tmp
            Else
                Exit For
            End If
        Next

 
 
 
 Re: Помогите понять смысл задания
Сообщение02.03.2010, 12:15 
Maslov в сообщении #293823 писал(а):
ewert в сообщении #293807 писал(а):
Во-первых, у Вас верхние границы циклов почему-то занижены на единицу (так, как если бы длина списка была (n-1), а не n).
С индексами всё нормально, просто они с 0 начинаются, а не с 1.
Поэтому всё-таки:
Код:
        Tmp = mis(n)
        For j = n-1 To 1 Step -1
            If Tmp < mis(j - 1) Then
                mis(j) = mis(j - 1)
                mis(j - 1) = Tmp
            Else
                Exit For
            End If
        Next



У меня так не выходит.
Просто у меня:
Код:
Dim y(0 To n - 1) As Single


и поэтому ошибка (Tmp = mis(n)) индекс находится вне границ массива...

 
 
 [ Сообщений: 21 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group