ТГиК-2019-Семинар-23.09.2019

Материал из Кафедра Прикладной Математики
Перейти к навигации Перейти к поиску

Разбор задач к 4 неделе

1.Расстояние хэмминга

Условие:

Расстояние Хэмминга между двумя целыми числами - это число позиций, в которых соответствующие биты различны. Учитывая два целых числа x и y, вычислить расстояние Хэмминга.

Примечание:

$$0≤x, y<2^{31}$$


Пример:

входные данные: х = 1, у = 4

выходные данные: 2

пояснение:

1 (0 0 0 1)

4 (0 1 0 0)

| |

Приведенные выше черточки указывают на позиции, в которых соответствующие биты отличаются.


Решение:

Мы можем использовать XOR (Exclusive OR), чтобы облегчить этот подсчет. Значение x^y сохраняет разницу, где разница является одним битом. И воспользуемся контейнером для работы с битами.

int hammingDistance(int x, int y) {
        int c=x^y;
        bitset<32> byte(c);
        return  byte.count();
    }

2.Возведение в целую степень

Условие:

Написать функцию, которая возводит x в степень n.


Пример1:

входные данные: 2.00000, 10

выходные данные: 1024.00000

Пример2:

входные данные: 2.10000, 3

выходные данные: 9.26100

Пример3:

входные данные: 2.00000, -2

выходные данные: 0.25000


Решение:

    double myPow(double x, long int n) {
        if (n < 0) {
           return  1/myPow (x, -n);
        } else if (n == 0) 
            return 1;
        double a = 1;
         while (n > 0) {
            if (n % 2 == 1) {
                 a *= x;
                n--;
            } 
            else{ 
                x *= x;
                n /= 2;
            }
        }
    return a;
    }

3.Корень из x

Условие:

Написать функцию, которая вычисляет квадратный корень их x.


Пример1:

Ввод: 4

Выход: 2

Пример2:

Ввод: 8

Выход: 2

Объяснение: десятичная часть усекается


Решение:

int mySqrt(int x) {
        long long s;
	for (s = 0; s * s <= x; ++s) {
		if (s * s == x) return s;
	} return s-1;    
    }

Можно так:

float Q_rsqrt( float number )
{
	long i;
	float x2, y;
	const float threehalfs = 1.5F;

	x2 = number * 0.5F;
	y  = number;
	i  = * ( long * ) &y;                       // evil floating point bit level hacking
	i  = 0x5f3759df - ( i >> 1 );               // what the fuck? 
	y  = * ( float * ) &i;
	y  = y * ( threehalfs - ( x2 * y * y ) );   // 1st iteration
//	y  = y * ( threehalfs - ( x2 * y * y ) );   // 2nd iteration, this can be removed

	return y;
}

4.Завершающие нули факториала

Условие:

Если задано целое число n, то верните количество завершающих нулей в n!.


Пример1:

Ввод: 3

Выход: 0

Объяснение: 3! = 6 - нет нулей

Пример2:

Ввод: 5

Выход: 1

Объяснение: 5! = 120 - один нуль


Решение:

Идея состоит в том, чтобы рассмотреть простые множители факториала n. Замыкающий ноль всегда является результатам произведения простых множителей 2 и 5. Если мы можем посчитать количество 5 и 2, наша задача выполнена. Рассмотрим следующие примеры.

n = 5: существует одна 5 и три 2 в простых множителях 5! (2 * 2 * 2 * 3 * 5). Поэтому количество нулей равно 1..

n = 11: есть два 5 и три 2 в простых множителях 11! (2 8 * 34 * 52 * 7). Таким образом, количество нулей равно 2.

Мы легко можем заметить, что число 2 в простых факторах всегда больше или равно числу 5, поэтому, если мы посчитаем 5 в простых факторах, мы решим задачу. Как подсчитать общее количество 5 в простых множителях n!? Простой способ-рассчитать количество (n / 5). Например, 7! есть один 5, 10! имеет два 5. Такие числа, как 25, 125 и т. д., имеют более одного 5. Например, если мы рассмотрим 28!, мы получаем один дополнительный 5 и число 0 встречается 6 раз. Обработка этого проста, сначала разделите n на 5 и удалите все одиночные 5, затем разделите на 25, чтобы удалить дополнительные 5 и так далее. Ниже приводится обобщенная формула для подсчета нулей.

int trailingZeroes(int n) {
        int k=0;
        long int i=5;
        while (n / i) {
            k+= n / i;
            i*=5;
        }
        return k;
}

5.Генерация всех перестановок длинны n

Условие:

Множество [1,2,3,...,n] содержит в общей сложности n! уникальные перестановки.

Перечисляя и помечая все перестановки по порядку, мы получаем следующую последовательность для n = 3:

1."123"

2."132"

3."213"

4."231"

5."312"

6."321"

Учитывая n и k, верните K-ю последовательность перестановок.


Примечание:

Данный n будет находиться между 1 и 9 включительно.

Учитывая, что k будет между 1 и n! включающий.

Пример1:

Ввод: n = 3, k = 3

Вывод: "213"

Пример2:

Ввод: n = 4, k = 9

Вывод: "2314"


Решение:

Лексикографический порядок.

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