skip to main content

kiesler.at

Hammingdistanz a la EPROG
updated by rck, 2004-11-06

Ich habe mal spaßhalber ein Programm aus der EPROG-Beispielsammlung umgesetzt. Es hat die Nummer 1074 und ermittelt die Hammingdistanz von ein paar übergebenen Codewörtern.

1 | 2 | 3 | 4 | 5 | 6

hammin.java

Hier als Referenz noch das gesamte Programm:

1 /*      hammin.java
2  *
3  *      Umsetzung des EPROG-Beispiels 1074 von
4  *      http://eprog.sourceforge.net/eprog/1074/Hammin.html
5  *
6  *      (c) 2004-09-07 http://www.kiesler.at/
7  *
8  */
9 
10 import java.io.*;
11 import java.util.StringTokenizer;
12 
13 import eprog.*;
14 
15 
16 public class hammin {
17 
18         private final static String SYNTACTIC_ERROR=" ?";
19         private final static String SEMANTIC_ERROR="FALSCHE EINGABE";
20 
21 
22 
23         /* is_binary prüft, ob der übergebene String
24          * tatsächlich nur aus 1 und 0 besteht.
25          *
26          * falls ja, wird true geliefert, sonst false
27          */
28 
29         public static boolean is_binary(String a)
30                 throws Exception {
31 
32                 for(int i=0; i
33                         if((a.charAt(i) != '0') && (a.charAt(i) != '1'))
34                                 return(false);
35 
36                 return(true);
37         }
38 
39 
40 
41         /* check_length prüft, ob der übergebene String
42          * tatsächlich die Länge len hat.
43          *
44          * falls ja, passiert nix. falls nein,
45          * wird eine exception geworfen.
46          */
47 
48         public static void check_length(String a, int len)
49                 throws Exception {
50 
51                 if(a.length() != len)
52                         throw new Exception(
53                                 "Eingabe "+a+" hat nicht die "+
54                                 "erforderliche Länge "+len);
55         }
56 
57 
58 
59         /* check_wordcount prüft, ob wir tatsächlich mindestens
60          * 2 bzw. maximal 8 wörter in der Eingabe haben. Das ist
61          * so in der Angabe verlangt!
62          *
63          * wenn ja, passiert nichts. wenn nein, gibt's eine Exception
64          */
65 
66         public static void check_wordcount(int wordcount)
67                 throws Exception {
68 
69                 if(wordcount < 2)
70                         throw new Exception(wordcount+
71                                 " Codewörter sind zu wenig!");
72 
73                 if(wordcount > 8)
74                         throw new Exception(wordcount+
75                                 " Codewörter sind zu viel!");
76         }
77 
78 
79 
80         /* check_termlen prüft, ob das abschließende Wort
81          * tatsächlich nur aus einem Zeichen besteht.
82          *
83          * Wenn ja, passiert nichts. wenn nein, gibt's eine Exception
84          */
85 
86         public static void check_termlength(String a)
87                 throws Exception {
88 
89                 int len=a.length();
90 
91                 if(len != 1)
92                         throw new Exception("Terminator darf "+
93                                 "nur 1 Zeichen lang sein, "+a+
94                                 "ist aber "+len+" Zeichen lang.");
95         }
96 
97 
98 
99         /* distance berechnet die hamming-distanz zwischen
100          * zwei wörtern.
101          *
102          * entspricht die länge nicht der gewünschten, gibt's
103          * eine exception.
104          *
105          * ACHTUNG! Länge & Gültigkeit des Strings sollten
106          * bereits geprüft worden sein!! (siehe auch
107          * check_binary() und check_length())
108          */
109         
110         public static int distance(String a, String b,
111                 int len) throws Exception {
112 
113                 int d=0;
114 
115                 for(int i=0; i
116                         if(a.charAt(i) != b.charAt(i))
117                                 d++;
118 
119                 return(d);
120         }
121 
122 
123 
124         /* get_wordlen holt sich die übergebene wortlänge aus
125          * einem String.
126          *
127          * handelt es sich um eine ungültige zahl, gibt's eine
128          * NumberFormatException.
129          *
130          * gilt nicht 1 <= zahl <= 4, gibt's eine Exception.
131          */
132 
133         public static int get_wordlen(String wordlen) 
134                 throws Exception {
135 
136                 // parseInt wirft eine NumberFormatException, falls
137                 // was nicht passt.
138 
139                 int len=Integer.parseInt(wordlen);
140 
141                 if(len < 1)
142                         throw new Exception("Wortlänge "+wordlen+
143                                         " zu klein!");
144 
145                 if(len > 4)
146                         throw new Exception("Wortlänge "+wordlen+
147                                         " zu groß!");
148 
149                 return(len);
150         }
151 
152 
153 
154         /* min liefert den kleineren der beiden
155          * übergebenen Integers zurück.
156          */
157 
158         public static int min(int a, int b) {
159                 if(a
160                         return(a);
161                 else
162                         return(b);
163         }
164 
165 
166 
167         /* distance(String) macht das gleiche wie
168          * distance(String, String, int): Die Hamming-Distanz
169          * berechnen.
170          *
171          * Wärend die distance(String, String, int) die Differenz
172          * zwischen zwei Strings berechnet, berechnet distance(String)
173          * die minimale Distanz der in der Angabe beschriebenen
174          * Gesamteingabe.
175          */
176 
177         public static String distance(String a) throws Exception {
178 
179                 // Was ist ein StringTokenizer ?
180                 // steht auf http://www.kiesler.at/article60.html
181                 StringTokenizer st=new StringTokenizer(a);
182 
183                 int len=get_wordlen(st.nextToken()), dist=len,
184                         words=2;
185 
186                 String prev=st.nextToken(), s=st.nextToken();
187                 check_length(prev, len);
188 
189                 while(is_binary(s)) {
190                         check_length(s, len);
191 
192                         dist=min(dist, distance(s, prev, len));
193 
194                         prev=s;
195                         s=st.nextToken(); words++;
196                 }
197 
198                 words--;        // der Terminator gilt nicht!
199 
200                 check_termlength(s);
201                 check_wordcount(words);
202 
203                 return(new Integer(dist).toString());
204         }
205 
206 
207         public static void main(String[] args) {
208                 // Nachdem die eprog-Bibliothek buggy ist
209                 // (siehe http://www.kiesler.at/article53.html)
210                 // hier die ausprogrammierte Variante.
211                 //
212                 // ist erlaubt, benutzt nur das JDK.
213 
214                 InputStreamReader ins=new InputStreamReader(System.in);
215                 BufferedReader reader=new BufferedReader(ins);
216 
217                 try {
218 
219                         EprogIO.println("HD="+distance(reader.readLine()));
220 
221                 } catch(NumberFormatException nfe) {
222 
223                         EprogIO.println(SYNTACTIC_ERROR);
224 
225                 } catch(Exception e) {
226 
227                         EprogIO.println(SEMANTIC_ERROR);
228 
229                 }
230         }
231 
232 }
1 | 2 | 3 | 4 | 5 | 6



RSSComments - Make a comment
The comments are owned by the poster. We are not responsible for its content.
RSSAll Articles
2008, 2007, 2006, 2005, 2004