Zabavno dejstvo iz sveta matematike
1/998001 nam da urejeno zaporedje od 000 do 999. 1/998001 = 0.000001002003004...

Zabavno dejstvo iz sveta računalništva
Leta 1936 so Rusi naredili računalnik na vodo. (Vir: http://gizmodo.com/5879106/the-russian-computer-that-ran-on-water)

3.1 de-FFT permutacija Topic is solved

Moderatorji: hinkopihpih, Matic Conradi

lukazlatecan
Site Admin
Prispevkov: 23
Pridružen: Po Apr 24, 2017 5:29 pm
Kraj: Celje

3.1 de-FFT permutacija

OdgovorNapisal/-a lukazlatecan » Če Maj 11, 2017 12:17 pm

Obveščevalna agencija sova se je odločila, da za šifriranje svojih sporočil ne bo zaupala ameriškim standardom, kot sta sha-2 in 3des. Raje so razvili lastno, novo kodirno funkcijo po imenu fft (Frišna Funkcija proti Terorju). fft zakodira podani niz znakov s1s2s3s4 . . . tako, da znake premeša po pravilu
fft(s1s2s3s4 . . .) = fft(s1s3s5 . . .) + fft(s2s4s6 . . .),
pri čemer + pomeni navadno stikanje nizov. Zgornja rekurzivna definicija velja za vse vhodne nize dolžine 2 ali več; za vhodne nize dolžine 1 pa nimamo česa premešati in definiramo kar fft(s1) = s1.

Primer 1:

Koda: Izberi vse

fft(sadje) = fft(sde) + fft(aj)
               = (fft(se) + fft(d)) + (fft(a) + fft(j))
               = ((fft(s)+fft(e))+d)+(a+j)
               = sedaj

Primer 2 (izpeljavo preskočimo):

Koda: Izberi vse

fft(kokain_crv) = krik_ovnac


Dokaži Sovi, da fft ni prav dobra šifra. Napiši program, ki dešifrira poljuben niz, zašifriran s fft.
Vhodna datoteka: v prvi vrstici je število n (1 ≤ n ≤ 100), število šifriranih spo- ročil. Vsaka od naslednjih n vrstic vsebuje po eno šifrirano sporočilo yi, sestavljeno izključno iz malih črk angleške abecede ter podčrtajev. Sporočila ne bodo daljša od 1024 znakov. V 30 % testnih primerov bodo vse dolžine sporočil potence števila 2.
Izhodna datoteka: vanjo po vrsti izpiši vseh n izvornih sporočil xi, vsako v svoji vrstici. To, da je xi „izvorno sporočilo“, pomeni, da velja zveza fft(xi) = yi.
Primer vhodne datoteke:

Koda: Izberi vse

9
sedaj
krik_ovnac
tutla_orask
avion_desno
desna_avtor
enak_nitro
lesk_oktav
uhan_serje
star_mivka

Pripadajoča izhodna datoteka:

Koda: Izberi vse

sadje
kokain_crv
tolsta_kura
adonis_oven
danost_reva
enkrat_oni
lokast_vek
usnjar_ehe
smrkav_ati
Mathematicians have tried in vain to this day to discover some order in the sequence of prime numbers, and we have reason to believe that it is a mystery into which the human mind will never penetrate. - Leonhard Euler

hinkopihpih
Prispevkov: 11
Pridružen: Ne Apr 30, 2017 2:11 pm

Re: 3.1 de-FFT permutacija  Topic is solved

OdgovorNapisal/-a hinkopihpih » Če Maj 11, 2017 8:01 pm

Koda: Izberi vse

import java.util.*;
import java.io.*;

public class deFFT
{
   public static void main(String[]args)
   {
      Scanner skan;
      File vhod;

      try
      {
         vhod = new File("defft.txt");
         skan = new Scanner(vhod);
      }
      catch(FileNotFoundException e)
      {
         skan = new Scanner(System.in);
      }

      String bla = skan.nextLine();
      int n = Integer.parseInt(bla);

      for(int i = 0; i < n; i++)
      {
         String s = skan.nextLine();
         String defft = desifriranje(s);
         System.out.println(defft);
      }
   }
   public static String desifriranje(String s)
   {
      int[] index = new int[s.length()];

      for(int i = 0; i < index.length; i++)
      {
         index[i] = i;
      }   

      index = permutacije(index).clone();

      char[] desifrirano = new char[s.length()];

      for(int i = 0; i < s.length(); i++)
      {
         desifrirano[index[i]] = s.charAt(i);
      }

      String resitev = "";

      for(int i = 0; i < s.length(); i++)
      {
         resitev = resitev + desifrirano[i];
      }

      return resitev;   
   }
   public static int[] permutacije(int[] index)
   {
      if(index.length == 1 || index.length == 0)
      {
         return index;
      }   

      int[] tab1;
      int[] tab2;

      if(index.length % 2 == 0)
      {
         tab1 = new int[index.length/2];
         tab2 = new int[index.length/2];
      }
      else
      {
         tab1 = new int[(int)(index.length/2) + 1];
         tab2 = new int[(int)(index.length/2)];   
      }   

      int count1 = 0;
      int count2 = 0;

      for(int i = 0; i < index.length; i++)
      {
         if(i % 2 == 0)
         {
            tab1[count1] = index[i];
            count1++;
         }
         else
         {
            tab2[count2] = index[i];
            count2++;
         }   
      }

      tab1 = permutacije(tab1).clone();
      tab2 = permutacije(tab2).clone();

      int[] resitev = new int[index.length];
      count1 = 0;
      count2 = 0;

      for(int i = 0; i < index.length; i++)
      {
         if(count1 == tab1.length)
         {
            resitev[i] = tab2[count2];
            count2++;
         }   
         else
         {
            resitev[i] = tab1[count1];
            count1++;
         }   
      }   

      return resitev;
   }
}


Vrni se na “2012”

Kdo je na strani

Po forumu brska: 0 registriranih uporabnikov in 1 gost