{ "cells": [ { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Zacetek programa: 1641741235.670977\n" ] } ], "source": [ "#Cilj je narest probram k bo ustvaril n tock in zracunal koliko je najvecje stavilo k presecisc ene premice vsemi daljicami.\n", "from random import randint\n", "import math\n", "import time\n", "seconds = time.time()\n", "print(\"Zacetek programa: \", seconds)\t\n", "\n", "\n", "\n", "###############################\n", "#Metoda je klass kjer je napisan algoritem za izracunavo c \n", "class Metoda : \n", " #stevilo_pik _ default\n", " n=5\n", " #sirina_okvirja _ default\n", " sirina=100 \n", "\n", " ############################\n", " # postavimo vse parametre \n", " polje= [] #polje tock\n", " tocke=[] #arraj za permutacijo daljic\n", " daljice=[] #trenutna permutacija na kateri racunam\n", " ar_daljice=[] #vse mozne permutacije daljic\n", "\n", " ############################\n", " #postavi random tocko v polje z sirino width\n", " def random_tocka(self,width, krog=False):\n", " if krog==True:\n", " return self.random_tocka_v_krogu(width)\n", "\n", " i = randint(0,width)\n", " j = randint(0,width)\n", " return i,j\n", "\n", " ############################\n", " #postavi random tocko v krog z polmerom width/2\n", " def random_tocka_v_krogu(self,width):\n", " i = randint(0,width)\n", " j = randint(0,width)\n", " w = width / 2\n", " ps = math.sqrt(j*j + (w-i)*(w-i))\n", " while (ps > w):\n", " j = randint(0,width)\n", " ps = math.sqrt(j*j + (w-i)*(w-i))\n", " return i,j\n", "\n", " ############################\n", " # to tocko zapisemo v array\n", " def dodaj_tocko(self,i,j):\n", " \n", " self.polje.append([i,j])\n", " \n", " def pobrisi_polje(self):\n", " self.polje = []\n", " #print(self.polje)\n", "\n", " def izpisi_polje (self):\n", " #print(self.polje)\n", " pass\n", "\n", " ############################\n", " # Z pomocjo zgornih funkcij zapise v arraj 2n tock\n", " def postavi_polje(self,stevilo_pik= 5, sirina_okvirja=100,krog=False): ## tu dodaj parametre\n", "\n", " self.pobrisi_polje()\n", " stevilo_pik *= 2\n", "\n", " for _ in range(stevilo_pik) :\n", " #self.izpisi_polje()\n", "\n", " i,j = self.random_tocka(sirina_okvirja,krog)\n", " while [i,j] in Metoda.polje :\n", " i,j = self.random_tocka(sirina_okvirja,krog)\n", " self.dodaj_tocko(i,j)\n", " #self.izpisi_polje()\n", "\n", "\n", " ############################\n", " \n", " #Matriko naredi za presek premice in daljice\n", " #vzemi 2 točke na premici in eno na daljici \n", " #vzemi 2 tocke na premico in eno na dalciji (tadrugo)\n", " #rabita ime nasprotni prednak\n", " \n", " def seka(self,l,d):\n", " #print (l)\n", " x = l[0]\n", " y = l[1]\n", " z1 = d[0]\n", " z2 = d[1]\n", " #print(self.polje[x][0])\n", " #print(self.polje[x][1])\n", " #print()\n", " #print()\n", " \n", " D1=matrix(SR, 3, [self.polje[x][0],self.polje[x][1],1,self.polje[y][0],self.polje[y][1],1,self.polje[z1][0],self.polje[z1][1],1])\n", " D2=matrix(SR, 3, [self.polje[x][0],self.polje[x][1],1,self.polje[y][0],self.polje[y][1],1,self.polje[z2][0],self.polje[z2][1],1])\n", " \n", " #print(D1)\n", " #print(D1.det())\n", " #print(D2)\n", " #print(D2.det())\n", " if D2.det() * D1.det() < 0 :\n", " return true \n", " else:\n", " return false\n", " \n", " \n", " \n", " def ustvari_daljice_v2 (self,n):\n", " self.daljice = [Set([i,j]) for i in range(2*n) for j in range(i+1, 2*n)] \n", " \n", " \n", " def program (self,n=5):\n", " p = MixedIntegerLinearProgram(maximization = False)\n", " \n", " \n", " x=p.new_variable(binary=True)\n", "\n", " p.set_objective(p[\"t\"])\n", "\n", " for i in range(2*n): \n", " p.add_constraint(sum(x[Set([i,j])] for j in range(2*n) if i != j) == 1)\n", "\n", " for l in self.daljice :\n", " p.add_constraint(sum(x[d] for d in self.daljice if self.seka(l,d)) <= p[\"t\"] )\n", "\n", " # ({3,4}, set([5,6]))\n", " #print (p.get_values(x)) # vrne vrednost x a)\n", " a = p.solve()\n", " #print (a) # vrne vrednost t ja\n", " return a\n", " \n", " \n", " \n", "\n", " \n", " \n", "\n" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "2\n", "2\n", "2\n", "2\n", "2\n" ] } ], "source": [ "seconds = time.time()\n", "nn=3\n", "for i in range(2,nn):\n", " for j in range(3*nn-2*i):\n", " a = Metoda ()\n", " a.postavi_polje(i)\n", " a.ustvari_daljice_v2(i)\n", " a.seka(a.daljice[0],a.daljice[1])\n", " b=a.program(i)\n", " seconds1 = time.time()\n", " print (i)\n", " #print (b/sqrt(i))\n", " #print (seconds1-seconds)\n" ] }, { "cell_type": "code", "execution_count": 0, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "2\n", "2 -daljic presecisc 1.0 C: 0.7071067811865476 cas: 0.009653806686401367\n", "3 -daljic presecisc 1.0 C: 0.5773502691896257 cas: 0.09989817937215169\n", "4 -daljic presecisc 1.0 C: 0.5 cas: 0.3965009053548177\n", "5 -daljic presecisc 1.0 C: 0.447213595499958 cas: 0.8445250193277994\n", "6 -daljic presecisc 1.0 C: 0.40824829046386296 cas: 2.0516225496927896\n", "7 -daljic presecisc 1.0000000000000002 C: 0.3779644730092273 cas: 3.6779468059539795\n", "8 -daljic presecisc 2.0000000000000004 C: 0.7071067811865477 cas: 6.533250570297241\n", "9 -daljic presecisc 2.0 C: 0.6666666666666666 cas: 10.39283021291097\n", "10 -daljic presecisc 2.0 C: 0.632455532033676 cas: 17.5063575108846\n", "11 -daljic presecisc 2.0 C: 0.6030226891555273 cas: 26.421429951985676\n", "12 -daljic presecisc 2.0 C: 0.5773502691896257 cas: 38.47291326522827\n", "13 -daljic presecisc 2.0 C: 0.5547001962252291 cas: 54.642125844955444\n", "14 -daljic presecisc 2.0 C: 0.5345224838248487 cas: 75.73027062416077\n" ] } ], "source": [ "import time\n", "\n", "seconds = time.time()\n", "st=2\n", "print(st)\n", "nn=20\n", "for i in range(st,nn):\n", " ar=[]\n", " cas=0\n", " for j in range(3):\n", " seconds = time.time()\n", " a = Metoda ()\n", " a.postavi_polje(i)\n", " a.ustvari_daljice_v2(i)\n", " a.seka(a.daljice[0],a.daljice[1])\n", " b=a.program(i)\n", " ar.append(b)\n", " \n", " seconds1 = time.time()\n", " cas += seconds1-seconds\n", " \n", " mm= max(ar)\n", " print (str(i), \"-daljic\",str( \"presecisc \"),str( mm ),\" C: \", str(float(mm/sqrt(i))), \"cas: \", cas/ (3))\n", " \n", "\n" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "2 -daljic presecisc 1.0 C: 0.7071067811865476 cas: 0.5147643884023031\n", "3 -daljic presecisc 1.0 C: 0.5773502691896257 cas: 0.06637001037597656\n", "4 -daljic presecisc 1.0 C: 0.5 cas: 0.18192736307779947\n", "5 -daljic presecisc 1.0 C: 0.447213595499958 cas: 0.41359424591064453\n", "6 -daljic presecisc 1.0 C: 0.40824829046386296 cas: 0.9518889586130778\n", "7 -daljic presecisc 2.0 C: 0.7559289460184544 cas: 1.466227928797404\n", "8 -daljic presecisc 2.0 C: 0.7071067811865476 cas: 2.807890017827352\n", "9 -daljic presecisc 2.0 C: 0.6666666666666666 cas: 4.203701098759969\n", "10 -daljic presecisc 2.0 C: 0.632455532033676 cas: 6.503405650456746\n", "11 -daljic presecisc 2.0 C: 0.6030226891555273 cas: 10.20706303914388\n", "12 -daljic presecisc 2.0 C: 0.5773502691896257 cas: 15.100358645121256\n", "13 -daljic presecisc 2.0 C: 0.5547001962252291 cas: 21.550816774368286\n", "14 -daljic presecisc 2.0 C: 0.5345224838248487 cas: 33.613250970840454\n", "15 -daljic presecisc 2.0 C: 0.5163977794943223 cas: 60.449558893839516\n", "16 -daljic presecisc 2.0 C: 0.5 cas: 78.31560269991557\n", "17 -daljic presecisc 2.0 C: 0.48507125007266594 cas: 83.93041729927063\n", "18 -daljic presecisc 3.0 C: 0.7071067811865476 cas: 6550.640018622081\n", "19 -daljic presecisc 3.0 C: 0.6882472016116853 cas: 12268.013555606207\n", "20 -daljic presecisc 3.0 C: 0.670820393249937 cas: 10521.755459070206\n" ] } ], "source": [ "import json\n", "nn=30\n", "\n", "with open(\"poganjanje-%d.json\" % nn) as f:\n", " for i, mm, cas in json.load(f):\n", " print (str(i), \"-daljic\",str( \"presecisc \"),str( mm ),\" C: \", str(float(mm/sqrt(i))), \"cas: \", cas/ (3))" ] }, { "cell_type": "code", "execution_count": 0, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": 0, "metadata": {}, "outputs": [], "source": [ "\n" ] }, { "cell_type": "code", "execution_count": 0, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": 0, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": 0, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": 0, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": 0, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": 0, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": 0, "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "SageMath 9.2.rc2", "language": "sage", "name": "sagemath" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.8.10" } }, "nbformat": 4, "nbformat_minor": 4 }