ФИИТ 1 курс. Языки программирования. C#


#42

Честно сказать, я его не понимаю.

А где алгоритм перекладывания? Какой диск перекладывать на какой стержень? Видимо, каждый st3.Push(st1.Pop()); надо еще выдавать 3->1

Но - в чём вкратце суть алгоритма?


#43

Рекурсия и yield return.

Когда мы проходили генерацию всех подмножеств, был такой код:

static IEnumerable<LinkedList<T>> GenIE<T>(T[] A, LinkedList<T> SubS = null, int i = 0)
{
   if (SubS == null)
      SubS = new LinkedList<T>();
   if (i == A.Length)
      yield return SubS; // работает не так, как мы хотим
   else
   {
      SubS.AddLast(A[i]);
      GenIE(A, SubS, i + 1); //вернёт пустую или одноэлементную последовательность сюда, а не в качестве продолжения изначальной последовательности
      SubS.RemoveLast();
      GenIE(A, SubS, i + 1);//возвращает новую последовательность, а не дополняет текущую
   }
}

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

static void Main(string[] args)
{
   WriteLine("Подмножества множества {4, 5, 6}:");
   foreach (var x in GenIE(new int[] { 4, 5, 6 }))
      x.Println(); //тело цикла не будет запущено
   WriteLine("Подмножества множества { }:");
   foreach (var x in GenIE(new int[] { }))
      x.Println(); //длина массива = 0 = i, последовательность будет состоять из одного элемента
      //и появится одна пустая строка
}

image

public static void Println<T>(this IEnumerable<T> a)
{
	foreach (var x in a)
		Write($"{x} ");
	WriteLine();
}

#45

В if я убрала условие, которое из-за выполнения сокращенного вычисления логического условия являлось лишним. Также я добавила вывод на экран действий, которые выполняет программа в каждом условии.


#46

А вот так работает:

static IEnumerable<LinkedList<T>> GenIE<T>(T[] A, LinkedList<T> SubS = null, int i = 0)
{
    if (SubS == null)
        SubS = new LinkedList<T>();
    if (i == A.Length)
        yield return SubS;
    else
    {
        SubS.AddLast(A[i]);
        foreach (var x in GenIE(A, SubS, i + 1))
            yield return x;
        SubS.RemoveLast();
        foreach (var x in GenIE(A, SubS, i + 1))
            yield return x;
    }
}

image


#47

Я ошибся конечно. Поспешил. Собственно, я исправлял код на доске. Не доисправил :frowning:

Код должен быть таким как Вы привели в последнем случае. Потому что любая функция должна возвращать значение. А если она вызывается как процедура - это подозрительно.


#48

Станислав Станиславович, опубликуйте, пожалуйста, презентацию с лекции по ООП


#49

Опубликовал. Как всегда - здесь: Вот ссылка на папку, где будут появляться все используемые презентации https://drive.google.com/drive/folders/1bcJ4Fdx2JBlq6A1RXPZiKjPQp7kfxZyG?usp=sharing


#50

Станислав Станиславович, можете, пожалуйста, опубликовать продолжение презентации?


#51

Сделал


#52

Олег, тетрадки с конспектами заберите пожалуйста у секретаря в деканате. Спасибо.


#53

Вот ссылка на конспект лекций:

https://drive.google.com/file/d/1QaTqCy8jTysqhMgyHLz0KNx9dgWqAOi9/view?usp=sharing8

Спасибо Олегу Арутюнову!


#54

Станислав Станиславович, выложите ,пожалуйста, программу экзамена.


#55

Программа курса “Языки программирования” 2 семестр 17-18 гг.

https://drive.google.com/file/d/1rajAAxwxi2v0Hid8_yGb9SVWHzEz-Gn5/view?usp=sharing


#56

“Необходимость опережающих объявлений при косвенной рекурсии.” в п.31 не актуалено для C#

Скриншот


#57

Да, недосмотрел. Исправил.


#58

Понял, спасибо, заберу


#59

Консультация 28 мая переносится с 17.00 на 18.30. Передайте пожалуйста всем.


#60

Станислав Станиславович, на лекции мы реализовывали Словарь на основе списка пар следующим образом:

 public class Dictionary<Key, Value>
        {
            private List<KeyValuePair<Key, Value>> l =
                new List<KeyValuePair<Key, Value>>();
            public Value this[Key k]
            {
                get
                {
                    int n = l.FindIndex(x => x.Key == k);
                    if (n >= 0)
                        return l[n].Value;
                    else
                        throw new KeyNotFoundException();
                }
                set
                {
                    int n = l.FindIndex(x => x.Key == k);
                    if (n >= 0)
                        l[n].Value = value;
                    else
                        l.Add(new KeyValuePair<Key, Value>(k, value));
                }
            }
        }

Однако при этом возникает две ошибки:

  1. Оператор "==" невозможно применить к операнду типа "Key" и "Key"
  2. Невозможно присвоить значение свойству или индексатору "KeyValuePair<Key, Value>.Value" — доступ только для чтения

Если первое можно как-то исправить, определив == для типа, то как быть со второй ошибкой?


#61

Да, вижу. Предлагаю следующее исправление:

public class Dictionary&lt;Key, Value&gt;
        {
            private List<KeyValuePair<Key, Value>> l =
                new List<KeyValuePair<Key, Value>>();
            public Value this[Key k]
            {
                get
                {
                    int n = l.FindIndex(x => x.Key == k);
                    if (n >= 0)
                        return l[n].Value;
                    else
                        throw new KeyNotFoundException();
                }
                set
                {
                    int n = l.FindIndex(x => x.Key.Equals(k));
                    if (n >= 0)
                        l[n]  = new KeyValuePair<Key, Value>(l[n].Key, value);
                    else
                        l.Add(new KeyValuePair<Key, Value>(k, value));
                }
            }
        }

Как второе сделать лучше - пока не знаю


#62

В программе экзамена в 57 пункте указано

  1. Реализация словаря на базе списка пар. Делегирование.

Но разве делегирование не относится к пункту 56?

  1. Реализация множества на базе бинарного дерева поиска.

Ведь именно при реализации множества класс MySortedSet делегировал вызовы своих методов классу BSTMethods