Раздел «Образование».FIVTLecturesTerm1Lecture2:
<<Лекции ФИВТ, 1-й семестр

Лекция 2. Анализ алгоритмов и понятие сложности вычислительной задачи. Задача сортировки и задача проверки числа на простоту.

Функции, операторы, переменные, типы, директивы препроцессора

Начинаем фиксировать свои знания в виде таблицы:

арифметические операторы + - * / %
операторы присваивания = += -= *= /= %=
логические операторы < > <= >= == != && ||
операторы структурного программирования if (A) { B } else { C }; while (A) {B}; for (A; B; C) { D }; do { A } while (B); break;
директивы препроцессора #include
базовые типы int, unsigned int, char, double, float и соответствующие им форматы %d %u %c %lf %f
стандартные функции printf, scanf

Задача проверки числа на простоту. Анализ времени работы. Нотация O(f(N)) и Theta(f(N))

Алгоритм проверки на простоту — проверяем делится ли n хотя бы на одно натуральное число из отрезка [2, sqrt(N)]. Оценка времени работы алгоритма.

Язык Си

На примере простых алгоритмических задач изучаем новые типы и новые операторы Типы

Операторы

Знакомимся с массивами на примере задачи вывода двоичной записи.

Код проверки числа на простоту

Код, использующий функцию sqrt из мат. библиотеки

#include <stdio.h>
#include <math.h>
int main() {
  int a, n;
  scanf("%d", &n);
  for (a = 2; a <= sqrt(n); a++) {
    if ( n % a == 0 ) break;
  }
  if ( n % a == 0 && n != a ) {
    printf("NO\n");
  } else {
    printf("YES\n");
  }
  return 0;
}

Команды компиляции и запуска программы:

bash$ gcc prime.c -lm -o prime
bash$ ./prime
11
YES
bash$ 

Какие значения следует проверить?

Код, не использующий функцию sqrt из мат. библиотеки

#include <stdio.h>
int main() {
  int a, n;
  scanf("%d", &n);
  for (a = 2; a * a <= n; a++) {
    if (n % a == 0) break;
  }
  if ( n % a == 0 && n != a ) {
    printf("NO\n");
  } else {
    printf("YES\n");
  }
  return 0;
}

Код, в котором определена отдельная функция проверки на простоту.

#include <stdio.h>

int is_prime(int n) {
  int a;
  for (a = 2; a * a <= n; a++) {
    if ( n % a == 0 ) break;
  }
  return (n % a != 0 && n != a);
}

int main() {
  int a, n;
  scanf("%d", &n);
  printf( is_prime(n) ? "YES\n" : "NO\n" );
  return 0;
}

Вывод ASCII кодов символов

#include <stdio.h>

int main() {
  int i;
  for ( i = 0; i < 256; i++ ) {
    printf("%d %c\n", i, i);
  }
  return 0;
}

Вывод двоичной записи числа

Код, который выводит двоичную запись задом наперёд.

#include <stdio.h>

int main() {
  int n;
  scanf("%d", &n);
  do {
    printf("%d", n % 2);
    n /= 2;
  } while ( n != 0 );
  printf("\n");
  return 0;
}

Код, который выводит двоичную запись в правильном порядке разрядов.

#include <stdio.h>

int main() {
  int n, i = 0;
  int result[100];
  scanf("%d", &n);
  do {
    result[i++] = n % 2;
    n /= 2;
  } while ( n != 0 );

  for ( i--; i >= 0 ; i-- ) {
    printf("%d", result[i]);
  }
  printf("\n");

  return 0;
}

Код, который выводит двоичную запись в правильном порядке разрядов и использует вывод строки (формат %s).

#include <stdio.h>

int main() {
  int n, i = 101;
  char result[101];

  result[100] = 0;

  scanf("%d", &n);

  do {
    result[--i] = '0' + (n % 2);
    n /= 2;
  } while ( n != 0 );

  printf("%s\n", &result[i]);

  return 0;
}