Пример пирамидальной сортировки на Си

 Пирамидальная сортировка.

 Два потомка у узла.

 /***
 Пирамидальная сортировка
 Пирамида - 2 потомка у узла имеют
 значение меньше чем у него. Таким
 образом, гарантированно можно извлечь
 наибольший элемент, затем пирамиду надо
 перебалансировать. Время - O(N*log2 N)


***/


#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define LEFT(i)  ((i<<1)+1)  //i*2 + 1
#define RIGHT(i) ((i<<1)+2)
#define SWAP(v,a,b)  {int tmp=v[a];v[a]=v[b];v[b]=tmp;}

void heapify(int v[], int i, int N){
 while(1){
  int left=LEFT(i), right=RIGHT(i), largest=i;
  if(left<N && v[left]>v[i]) largest=left;
  if(right<N && v[right]>v[largest])largest=right;
  if(largest!=i){
    SWAP(v,i,largest);
    i = largest;
  }else
    return;
 }
}
int pop(int v[],int N){
  if(N<=0)
    return -1;
  int top = v[0];
  v[0] = v[N-1];
  heapify(v,0,N-1);
  return top;
}
void heapSort(int v[],int N){
  int i = (N-2)/2;
  while(i>=0){
    heapify(v,i--,N);
  }
}

void heapSort1(int v[],int N){
  int i,index,parent;
  for(i = 0; i < N;i++){
    index=i;
    while(index!=0){
      parent = (index-1)/2;
      if(v[index]<=v[parent])
        break;
      SWAP(v,index,parent);
      index=parent;
    }
  }
}

#define N 10
int main(){
 int v[N];
 int j;
 
 srand(time(0));
 for(j=0;j<N;j++)
  v[j] = rand()%20;

 heapSort1(v,N);
 for(j = N; j > 0; j--)
   printf("%d, ", pop(v,j));
 printf("\n");

 return 0;
}
------------------------------------

 

4 потомка у узла.

/***
 Пирамидальная сортировка
 Пирамида - 4 потомка у узла имеют
 значение меньше чем у него. Таким
 образом, гарантированно можно извлечь
 наибольший элемент, затем пирамиду надо
 перебалансировать. Время - O(N*log4 N)


***/


#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define NEXT1(i) ((i<<2)+1)  //i*4 + 1
#define NEXT2(i) ((i<<2)+2)
#define NEXT3(i) ((i<<2)+3)
#define NEXT4(i) ((i<<2)+4)

#define SWAP(v,a,b)  {int tmp=v[a];v[a]=v[b];v[b]=tmp;}

void heapify(int v[], int i, int N){
 while(1){
  int n1=NEXT1(i),
      n2=NEXT2(i),
      n3=NEXT3(i),
      n4=NEXT4(i),
      largest=i;
  if(n1<N && v[n1]>v[largest])largest=n1;
  if(n2<N && v[n2]>v[largest])largest=n2;
  if(n3<N && v[n3]>v[largest])largest=n3;
  if(n4<N && v[n4]>v[largest])largest=n4;
 
  if(largest!=i){
    SWAP(v,i,largest);
    i = largest;
  }else
    return;
 }
}
int pop(int v[],int N){
  if(N<=0)
    return -1;
  int top = v[0];
  v[0] = v[N-1];
  heapify(v,0,N-1);
  return top;
}
void heapSort(int v[],int N){
  int i = (N-2)/4;
  while(i>=0){
    heapify(v,i--,N);
  }
}


void heapSort1(int v[],int N){
  int i,index,parent;
  for(i = 0; i < N;i++){
    index=i;
    while(index!=0){
      parent = (index-1)>>2; //    /4
      if(v[index]<=v[parent])
        break;
      SWAP(v,index,parent);
      index=parent;
    }
  }
}

#define N 10
int main(){
 int v[N];
 int j;
 
 srand(time(0));
 for(j=0;j<N;j++)
  v[j] = rand()%20;

 heapSort1(v,N);
 for(j = N; j > 0; j--)
   printf("%d, ", pop(v,j));
 printf("\n");

 return 0;
}
 

Обучение с подкреплением, пример на си

 Вот пример реализации простого обучения с подкреплением на языке C, где агент учится выбирать между двумя действиями с разными вероятностями получения награды:

```c

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

int main() {

    srand(time(NULL)); // Инициализация генератора случайных чисел

    // Параметры обучения

    double Q[2] = {0.0, 0.0};    // Q-значения для двух действий

    double alpha = 0.1;          // Скорость обучения

    double epsilon = 0.1;        // Вероятность исследования

    int episodes = 1000;         // Количество эпизодов

    int action_counts[2] = {0};  // Счетчик выбора действий

    // Процесс обучения

    for (int episode = 0; episode < episodes; episode++) {

        int action;

        

        // ε-жадный выбор действия

        if ((double)rand() / RAND_MAX < epsilon) {

            action = rand() % 2; // Случайное действие (исследование)

        } else {

            // Жадный выбор (использование)

            action = (Q[0] > Q[1]) ? 0 : 1;

        }

        action_counts[action]++;

        // Генерация награды

        int reward;

        if (action == 0) {

            // Действие 0: 70% chance +1, 30% chance -1

            reward = (rand() % 100 < 70) ? 1 : -1;

        } else {

            // Действие 1: 30% chance +1, 70% chance -1

            reward = (rand() % 100 < 30) ? 1 : -1;

        }

        // Обновление Q-значения

        Q[action] += alpha * (reward - Q[action]);

    }

    // Вывод результатов

    printf("Обучение завершено!\n");

    printf("Q-значения: [Действие 0: %.2f, Действие 1: %.2f]\n", Q[0], Q[1]);

    printf("Выбор действий: [Действие 0: %d раз, Действие 1: %d раз]\n", 

           action_counts[0], action_counts[1]);

    return 0;

}

```

Этот код демонстрирует:

1. **ε-жадную стратегию** выбора действий (10% случайные действия для исследования)

2. **Обновление Q-значений** по правилу:  

   `Q(a) ← Q(a) + α * (reward - Q(a))`

3. **Среду с разными вероятностями** наград:

   - Действие 0: +1 (70%), -1 (30%)

   - Действие 1: +1 (30%), -1 (70%)

После 1000 эпизодов агент должен:

- Показать более высокое Q-значение для действия 0

- Выбирать действие 0 значительно чаще

Пример вывода:

```

Обучение завершено!

Q-значения: [Действие 0: 0.42, Действие 1: -0.31]

Выбор действий: [Действие 0: 873 раз, Действие 1: 127 раз]

```

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