using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace new_lr_1_var_12 {
	class Program {
		const int m = 44;
		const int n = 4;

		static int HashFunction(int key) {
			return Convert.ToInt16(key % Convert.ToInt16(1.5 * m));
		}
		static void Main(string[] args) {
			int t = Convert.ToInt16(1.5 * m);
			Random rnd = new Random();
			int[] keys = new int[t];
			Console.Write(" Исходные ключи: \n");
			for (int i = 0; i < m; ++i) {
				keys[i] = rnd.Next(Convert.ToInt16(Math.Pow(10, n - 1)), Convert.ToInt16(Math.Pow(10, n)));
				Console.Write("key=" + keys[i] + " h(" + keys[i] + ")=" + HashFunction(keys[i]) + " ");
				if ((i + 1) % 4 == 0) Console.WriteLine();
			}

			int[] hasht = new int[t];
			for (int i = 0; i < t; ++i)
			hasht[i] = 0;
			int k = m;
			for (int j = 0; j < m; ++j) {
				if (hasht[HashFunction(keys[j])] == 0) hasht[HashFunction(keys[j])] = keys[j];
				else {
					for (int i = 1;; ++i) {
						++k;
						if (hasht[(HashFunction(keys[j]) + i * i) % t] == 0) {
							hasht[(HashFunction(keys[j]) + i * i) % t] = keys[j];
							break;
						}
					}

				}
			}
			Console.Write("\n Хеш-таблица: \n");
			for (int i = 0; i < t; ++i) {
				Console.Write("[" + i + "]:" + hasht[i] + " ");
				if ((i + 1) % 7 == 0) Console.WriteLine();
			}
			Console.Write("\n Коэффициент заполнения = " + Convert.ToDouble(m) / Convert.ToDouble(t));
			Console.Write("\n Среднее число проб = " + Convert.ToDouble(k) / Convert.ToDouble(m));
			Console.ReadKey();
		}
	}
}