SHARE
TWEET

Untitled

a guest Oct 16th, 2019 80 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. using System.Text;
  5. using System.Threading.Tasks;
  6.  
  7. namespace Lab_3._2
  8. {
  9.     class Program
  10.     {
  11.         static void Main(string[] args)
  12.         {
  13.             Console.WriteLine("Введите N");
  14.             int N = int.Parse(Console.ReadLine());
  15.             Console.WriteLine("Введите k");
  16.             int k = int.Parse(Console.ReadLine());
  17.             var watch = System.Diagnostics.Stopwatch.StartNew();
  18.             watch.Start();
  19.             Console.WriteLine(Flavy(N, k));
  20.             watch.Stop();
  21.             Console.WriteLine(watch.ElapsedMilliseconds + " мс - массив");
  22.             watch.Restart();
  23.             Console.WriteLine(ListFlavy(N, k));
  24.             watch.Stop();
  25.             Console.WriteLine(watch.ElapsedMilliseconds + " мс - связный список");
  26.             Console.ReadLine();
  27.         }
  28.  
  29.  
  30.         static int Flavy(int N, int k)
  31.         {
  32.             bool[] arr = new bool[N];
  33.             for (int i = 0; i < N; i++)
  34.                 arr[i] = true;
  35.             int count = 1;
  36.             int index = 0;
  37.             int aliveCount = N;
  38.             while (aliveCount > 1)
  39.             {
  40.                 if (index == N)
  41.                     index = 0;
  42.  
  43.                 if (!arr[index])
  44.                 {
  45.                     index++;
  46.                     continue;
  47.                 }
  48.                 if (count == k && arr[index] == true)
  49.                 {
  50.                     arr[index] = false;
  51.                     count = 0;
  52.                     aliveCount--;
  53.                 }
  54.                 index++;
  55.                 count++;
  56.             }
  57.             int alive = -1;
  58.             for (int i = 0; i < N; i++)
  59.                 if (arr[i])
  60.                     alive = i;
  61.             return alive + 1;
  62.         }
  63.  
  64.         static int ListFlavy(int N, int k)
  65.         {
  66.             LinkedList<int> items = new LinkedList<int>();
  67.             for (int i = 1; i <= N; i++)
  68.                 items.AddLast(i);
  69.             int count = 1;
  70.             var node = items.First;
  71.             while (items.Count > 1)
  72.             {
  73.                 var next = node.Next;
  74.                 if (count == k)
  75.                 {
  76.                     items.Remove(node);
  77.                     count = 0;
  78.                 }
  79.                 count++;
  80.                 if (next == null)
  81.                     node = items.First;
  82.                 else
  83.                     node = next;
  84.             }
  85.             return items.First.Value;
  86.         }
  87.     }
  88. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top