Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // Notkun: b = isInPowerArray(x,i,y);
- // Fyrir: x er strengur sem inniheldur aðeins stafina
- // a,b,...,z (enska stafrófið). Enginn
- // stafur er endurtekinn í strengnum og
- // stafirnir eru í stafrófsröð. Lengd
- // strengsins er því á bilinu 0..26.
- // i er hvaða heiltala sem er, y er strengur.
- // Eftir: b er satt þá og því aðeins að veldisfylki
- // strengsins x hafi strenginn y í sæti i.
- static public boolean isInPowerArray( String x, int i, String y )
- {
- // skilyrði er að 0<=i
- if ((i<0) )
- {
- return false;
- }
- // Það eru vandamál með að x.charAt(0) fyrir núllstrenginn svo við meðhöndlum hann sérstaklega.
- if (y == "")
- {
- // Núllstrengurinn er alltaf í núllta sæti.
- if (i == 0)
- {
- return true;
- }
- return false;
- }
- // ATH! a == b gáir hvort a og b séu sami hluturinn, a.equals(b) gáir hvort a og b hafi sama gildi
- // það vantar núllstrenginn í Power(x), það byrjar á "a" svo indexið hliðrast um 1
- if (Power(x)[i-1].equals(y))
- {
- return true;
- }
- // else
- return false ;
- }
- // Notkun: a = Power(x);
- // Fyrir: x er strengur sem inniheldur stafi
- // a..z í stafrófsröð, núll eða fleiri.
- // Hver stafur má í mesta lagi koma fyrir
- // einu sinni.
- // Eftir: a vísar á veldisfylki strengsins x, að núllstrengnum undanskildnum. length.a == 2^(x.length())-1
- // Fallið er endurkvæmt og byggir á eftirfarandi staðreynd:
- // Veldisfylki x = fylkið sem inniheldur fremsta staf x bætt við sérhvert stak í veldisfylki x.substring(0,1) auk veldisfylkis x.substring(0,1)
- // t.d. er P(c) = {"", "c"}
- // P(bc) = {bc, b} auk {"", "c"}
- // P(abc) = {a, ab, ac, abc} auk {b, bc, c, ""}
- // Það er skemmtilegt við þessa aðferð er að stökin koma út í stafrófsröð.
- static public String[] Power( String x )
- {
- // Hvað gerist ræðst alfarið af því hversu langur strengurinn x er
- int k = x.length();
- // Grunnur. Fallið verður að taka eitthvað grunngildi. dæmi: Power(abc) kallar á Power(bc) sem loks kallar á Power(c) sem skilar {c}
- // Ath. það er ekki það sama og veldisfylki "c" því tómi strengurinn er ekki með í úttakinu. En það er ekki vandamál.
- if (k == 1)
- {
- String[] res1 = {x};
- return res1;
- }
- int m = (int)Math.pow(2,k) ; // fjöldi staka í veldisfylkinu P(x)
- int s = (int)Math.pow(2,k-1); // fjöldi staka í P(x.substring(1))
- String[] res = new String[m-1]; // hlöðum gildunum inn í 2^k-1 staka fylki sem verður úttakið (result)
- String x0 = Character.toString(x.charAt(0)); // Fremsti stafurinn í x, sem þarf að vinna sérstaklega með. ath. Munur er á staf og strengnum sem inniheldur stafinn
- String[] substr = Power(x.substring(1)); // köllum á fallið fyrir substrenginn bara einu sinni. Ef þetta er gert inni í lykkjunum kemur timeout!
- res[0] = x0; // Þar sem við vinnum ekki með tóma strenginn þarf að setja fremsta stafinn inn í fylkið í hverju skrefi.
- // Til að finna veldisfylkið viljum við skeyta x0 við öll stök veldisfylkis x.substring(1), en Power(x) inniheldur aldrei tóma strenginn.
- // Dæmi: P(bc) inniheldur b því "b" + "" == "b"
- // Það eru 2^k = 2^(k-1)+2^(k-1) stök í veldisfylkinu.
- // Helmingur stakanna í veldisfylkinu P(x) eru fremsti stafurinn í x skeyttur saman við sérhvert stak P(x.substring(1))
- // 1 <= i < 2^(k-1)
- for(int i = 1; i < s; i++)
- { // Fastayrðing lykkju: res[i-1] er i-ta stak (talið frá 0) veldisfylkisins P(x).
- // ath. fastayrðingin segir til um ástandið eftir að i hefur fengið gildi fyrir umferðina en áður en nokkuð gerist
- // dæmi: x = "abc", i = 3, res[i-1] = "abc"
- // P(x) = {"", "a", "ab", "abc", "ac, "b", "bc", "c"} P(x.substring(1)) = {"", "b", "bc", "c"}
- // i = 1, res[i-1] = "a"
- res[i] = x0 + substr[i-1]; // Byrjum á 0. staki substrengsins
- }
- // Hinn helmingurinn eru stökin úr P(x.substring(1))
- // 2^(k-1) <= j < 2^k
- for(int j = s; j< m-1 ; j++)
- { // Fastayrðing lykkju: res[j-1] er j-ta stak P(x).
- // dæmi: x = "abc", j = 4, res[j-1] = "ac"
- // P(x) = {"", "a", "ab", "abc", "ac, "b", "bc", "c"} P(x.substring(1)) = {"", "b", "bc", "c"}
- // j = 6, res[j-1] = b
- res[j] = substr[ j-s ]; // Byrjum á 0. staki substrengsins
- }
- return res;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement