Buch Cover Buch Cover Buch Cover Buch Cover

Web-Code: - Webcode Help

Buchstabensalat (Schleifen)

Schreib ein Programm das in einem Buchstabensalat z. B. "sakdeidpoidweoidowijk" den längsten Substring in alphabetisch-korrekter Reihenfolge findet.

 

z. B. "kotafgovlav" -> "Der längste alphabetische Substring ist: afgov"

 

gibt es 2 gleichlange Kandidaten, soll der erste genommen werden

z.B. "abcbcd" -> "Der längste alphabetische Substring ist: abc"

4 Kommentare

Bitte melde dich an um einen Kommentar abzugeben

Kommentare (4)

gressly 28. Oktober 2013 11:21   reply report
Coole Aufgabe.

Könnte man für Primarschüler der zweiten Klasse noch etwas anders formulieren: Buchstabensuppe (statt Salat). Auf dem Tellerrand liegen zufällig herausgepickte Buchstaben. Um das Alphabeth zu lernen sucht XY nun die längste aufsteigende Buchstabensequenz und darf diese dann gleich essen ;-)
peter 28. Oktober 2013 02:18   reply report
peter
python
Hi - ich versteh nicht ganz wie Dein Code funktioniert. Denn was passiert bei dem string "abcdef"? (ungetestet) - Sieh dir das nochmal genau an.

Ah, danke für den Hinweis. Ist mir beim testen nicht aufgefallen.

Habs ausgebessert, nochmals getestet und müsste jtz alle Fälle abdecken.


Hab im 'if' - if str == atoz: mem=str

ersetzt durch (wie beim else) - if len(str) > len(mem): mem=str

..ich denke beim else könnte man das if auch ganz weglassen.
peter 28. Oktober 2013 02:10   reply report
python
Hi - ich versteh nicht ganz wie Dein Code funktioniert. Denn was passiert bei dem string "abcdef"? (ungetestet) - Sieh dir das nochmal genau an.

Ah, danke für den Hinweis. Ist mir beim testen nicht aufgefallen.

Habs ausgebessert, nochmals getestet und müsste jtz alle Fälle abdecken.


Hab im 'if' - if str == atoz: mem=str

ersetzt durch (wie beim else) - if len(str) > len(mem): mem=str
python 27. Oktober 2013 19:48   reply report
Hi - ich versteh nicht ganz wie Dein Code funktioniert. Denn was passiert bei dem string "abcdef"? (ungetestet) - Sieh dir das nochmal genau an.

9 Lösung(en)

salat=raw_input("Geben sie eine willkuerliche Buchstabenkombination ein: ")
atoz=('abcdefghijklmnopqrstuvwxyz')
pos=0
str=''
mem=''
for let1 in salat:
	ct=-1
	for let2 in atoz:
		ct += 1
		if let1 == let2:
			if ct >= pos:
				str=str + let1
				pos=ct
				if len(str) > len(mem):
					mem=str
				break
			else:
				if len(str) > len(mem):
					mem=str
				str=let1
				pos=ct
				break
print ("Der laengste Substring in alphabetischer Reihenfolge ist: " + mem)
                

Lösung von: Name nicht veröffentlicht

package ch.programmieraufgaben.iteration.buchstabensalat;

import java.util.Scanner;

/**
 * Aufgabe Buchstabensalat (www.programmieraufgaben.ch) Web-Code n5jh-p4n3
 * 
 * @author philipp.gressly @ santis.ch
 * 
 */
public class Buchstabensalat {
	public static void main(String[] args) {
		new Buchstabensalat().top();
	}

	Scanner sc = new Scanner(System.in);

	String eingeben(String frage) {
		System.out.println(frage);
		return sc.next();
	}

	void top() {
		String eingabe = eingeben("Bitte Buchstabensalat eingeben: ");
		int aktMaxPos = 0;  // aktuelle Position mit dem längsten String (minimal
							// Länge 1 wird er wohl haben ab pos 0)
		int aktMaxLen = laengeAlphabetischAbPos(aktMaxPos, eingabe);
		int tempPos   = aktMaxPos + aktMaxLen;
		// Brauche nicht mehr zu probieren, wenn am Ende nur noch weniger
		// Zeichen sind,
		// als bereits als längster String gefunden wurden.
		while (tempPos < eingabe.length() - aktMaxLen) {
			int tempLen = laengeAlphabetischAbPos(tempPos, eingabe);
			if (tempLen > aktMaxLen) {
				aktMaxLen = tempLen;
				aktMaxPos = tempPos;
				tempPos   = aktMaxPos + aktMaxLen;
			} else {
				tempPos = tempPos + tempLen;
			}
		}
		ausgabe(aktMaxPos, aktMaxLen, eingabe);
	}

	void ausgabe(int pos, int len, String salat) {
		System.out.println("Der längste aufsteigende Substring wird mit Länge "
				+ len + " an Position " + pos + " gefunden: \""
				+ salat.substring(pos, pos + len) + "\"");
	}

	/**
	 * Anzahl Zeichen, welche alphabetisch aufsteigen
	 * 
	 * @param pos
	 *            ab wo durchsuchen
	 * @param zuDurchsuchenderSalat
	 * @return mindestens eins.
	 */
	int laengeAlphabetischAbPos(int pos, String zuDurchsuchenderSalat) {
		int tmpPos = pos;
		while (tmpPos + 1 < zuDurchsuchenderSalat.length()
				&& zuDurchsuchenderSalat.charAt(tmpPos) <= zuDurchsuchenderSalat.charAt(tmpPos + 1)) {
			tmpPos = tmpPos + 1;
		}
		return tmpPos - pos + 1;    // AnzahlZeichen = max-min + 1 (wie beim Zaun, da
									// braucht es immer einen Pfosten mehr als
									// Drähte.)
	}
}

                

Lösung von: Philipp G. Freimann (BBW (Berufsbildungsschule Winterthur) https://www.bbw.ch)

# -*- coding: UTF-8 -*-


def main():
    str = "kotafgovlav" # kotafgovlav # abcbcd # abcdef
    
    
    str += "\x00"
    longest = ""
    
    for i in range(len(str)):
        x = 0
        tmp = ""
        for c in str[i:]:
            if ord(c) > x:
                x = ord(c)
                tmp += c
            else:
                if (len(tmp) > len(longest)):
                    longest = tmp
                
                break
    
    
    print(longest)



if __name__ == "__main__":
    main()

                

Lösung von: Name nicht veröffentlicht

#include <stdio.h>
#include <iostream> //malloc()

/*
    Gelöst mit verketteter Liste
*/

struct Datensatz   //Liste von Datensätzen die später verglichen werden
{
    int position; //damit ist die Position im Char-Array gemeint
    int laenge;

    Datensatz *next;
};
struct Datensatz* listenElementHinzu(struct Datensatz *kopf, int position, int laenge)
{
    struct Datensatz *neu = (struct Datensatz*) malloc(sizeof(struct Datensatz));
    neu->position   = position;
    neu->laenge     = laenge;

    neu->next = kopf->next;
    kopf->next = neu;

    return neu;
}

struct Datensatz sucheLaengstenSubstring(struct Datensatz *kopf)
{
    struct Datensatz *aktuell = kopf;

    struct Datensatz laengste;
    laengste.laenge     = kopf->laenge;
    laengste.position   = kopf->position;
    laengste.next       = NULL;


    while(aktuell->next != NULL)
    {
        if(laengste.laenge <= aktuell->laenge)
        {
            laengste.laenge = aktuell->laenge;
            laengste.position = aktuell->position;
        }

        aktuell = aktuell->next;
    }
    //Das Letzte Listenelement muss nochmal überprüft werden, da er in der while schleife den nächsten überprüft
    if(laengste.laenge <= aktuell->laenge)
    {
            laengste.laenge = aktuell->laenge;
            laengste.position = aktuell->position;
    }

    return laengste;
}

struct Datensatz laengsterSubstring(struct Datensatz *kopf, char *eingabe)
{
    int i;
    struct Datensatz *aktuell = kopf;


    for(i = 0; *eingabe != '\0'; i++, eingabe++) 
    {
        if(*(eingabe+1) != '\0')
        {
            if(*eingabe <= *(eingabe+1))
            {
                aktuell->laenge++;
            }
            else
            {
                aktuell = listenElementHinzu(kopf, aktuell->position+aktuell->laenge, 1);
            }
        }
        else
        {
            break;
        }
    }

    return sucheLaengstenSubstring(kopf);
}

int main()
{
    char eingabe[100];

    printf("Bitte String eingeben: ");
    gets(eingabe); fflush(stdin);

    struct Datensatz kopf; //Listenanfang
    kopf.position   = 0;
    kopf.laenge     = 1;
    kopf.next       = NULL;


    struct Datensatz l = laengsterSubstring(&kopf, eingabe);

    printf("Laengster Substring: ");

    int i;
    for( i = l.position; i < l.laenge+l.position; i++)
        printf("%c", eingabe[i]);


   return 0;
}

                

Lösung von: Christian :) (Hochschule Merseburg)

DCL INPUT CHAR(20) INIT('ASDMQWOPVMWPVSDKFVMS'); /* Test-Input */      
                                                                       
/* Input kann variabel sein, deshalb umfüllen in VARCHAR */            
/* Maximal-Länge ist hier mit 1000 Byte deklariert */                  
DCL ZW_TESTSTR   CHAR(1000) VAR INIT('');                              
DCL ZW_TESTPOS1  PTR;                                                  
DCL ZW_TESTPOS2  PTR;                                                  
DCL ZW_TESTCH1   CHAR(1) BASED(ZW_TESTPOS1);                           
DCL ZW_TESTCH2   CHAR(1) BASED(ZW_TESTPOS2);                           
DCL IND1         BIN FIXED(31) INIT(0);                                
DCL ZW_START     BIN FIXED(31) INIT(1);                                
DCL ZW_ENDE      BIN FIXED(31) INIT(1);                                
DCL ZW_START_S   BIN FIXED(31) INIT(0);                                
DCL ZW_ENDE_S    BIN FIXED(31) INIT(0);                                
                                                                       
/* Input einlesen */                                                   
ZW_TESTSTR  = INPUT;                                                   
PUT SKIP LIST(ZW_TESTSTR !! ' wird geprüft');                          
                                                                       
/* Leeren Input abfangen */                                            
IF(LENGTH(ZW_TESTSTR) = 0) THEN DO;                                    
  PUT SKIP LIST('INPUT ist leer');                                     
  RETURN;                                                              
END;                                                                   
                                                                       
/* Prüfung für Input mit Länge 1 unterbinden */                        
IF(LENGTH(ZW_TESTSTR) = 1) THEN DO;                                    
  PUT SKIP LIST('Der längste alphabetische Substring ist: ' !!         
                TRIM(ZW_TESTSTR));                                     
  RETURN;                                                              
END;                                                                   
                                                                       
/* Positionsmarker setzen */                                           
/* VARCHAR hat 2 Byte Header für die Länge */                          
ZW_TESTPOS1 = ADDR(ZW_TESTSTR);                                        
ZW_TESTPOS2 = ADDR(ZW_TESTSTR);                                        
ZW_TESTPOS1 += 1;                                                      
ZW_TESTPOS2 += 2; /* Position auf 1. Zeichen im Inhalt setzen */       
                                                                       
/* Eigentliche Verarbeitung */                                         
DO IND1 = 2 TO LENGTH(ZW_TESTSTR);                                     
  ZW_TESTPOS1 += 1; /* auf nächste relevante Stelle positionieren */   
  ZW_TESTPOS2 += 1; /* auf nächste relevante Stelle positionieren */   
  IF ZW_TESTCH2 > ZW_TESTCH1 THEN DO;                                  
    /* Noch in alphabetischer Reihenfolge */                           
    ZW_ENDE = IND1;                                                    
  END;                                                                 
  ELSE DO;                                                             
    /* Nicht mehr in alphabetischer Reihenfolge */                     
    /* Übernehmen, falls länger */                                     
    IF (ZW_ENDE - ZW_START + 1) >                                      
       (ZW_ENDE_S - ZW_START_S + 1 ) THEN DO;                          
      ZW_START_S = ZW_START;                                           
      ZW_ENDE_S  = ZW_ENDE;                                            
    END;                                                               
    ZW_START = IND1; /* Start neu setzen */                            
  END;  /* Ende ELSE */                                                              
END; /* Ende LOOP */                                                                
                                                                       
/* End-Verarbeitung. Übernehmen, falls länger */                       
IF (ZW_ENDE-ZW_START) > (ZW_ENDE_S-ZW_START_S) THEN DO;                
  ZW_START_S = ZW_START;                                               
  ZW_ENDE_S  = ZW_ENDE;                                                
END;                                                                   
                                                                       
/* Ausgabe */                                                          
PUT SKIP LIST('Der längste alphabetische Substring ist: ' !!           
              SUBSTR(ZW_TESTSTR,ZW_START_S,(ZW_ENDE_S-ZW_START_S+1))); 
RETURN;                                                                
                                                                       
                

Lösung von: Valentin Marolf (AXA)

import java.util.Scanner;

public class Aufgabe1_Buchstabensuppe {
	
	public static void main(String[] args){
		Scanner in = new Scanner(System.in);
		
		System.out.print("Geben sie eine Buchstabenfolge ein:");
		String eingabe = in.nextLine();
		
		String temp = "";
		String laengsteFolge = "";
		int anzahlBuchstaben = 0;
		
		for (int i = 0; i < eingabe.length(); i++) {
			if(anzahlBuchstaben != 0){
				char next = eingabe.charAt(i);
				if(next > temp.charAt(temp.length()-1)){
					temp += next;
					anzahlBuchstaben++;
					if(temp.length() > laengsteFolge.length()){
						laengsteFolge = temp;
					}
				} else {
					temp = String.valueOf(next);
					anzahlBuchstaben = 1;
				}
			} else {
				temp = String.valueOf(eingabe.charAt(i));
				anzahlBuchstaben++;
			}
		}
		
		if(anzahlBuchstaben <= 1){
			System.out.println("Die Eingabe \"" + eingabe + "\" enthält keine Buchstabenfolge.");
		} else {
			System.out.println("Die längste Buchstabenfolge in \"" + eingabe + "\" ist: " + laengsteFolge + ".");
		}
	}

}
                

Lösung von: Name nicht veröffentlicht

#include <stdio.h>
#include <stdint.h>
#include <stdbool.h>
#include <stdlib.h>

void longest_ascending_substring( char str[], int32_t* begin, int32_t* length );
char to_lower_case( char c );
bool is_lower_case_letter( char c );

//Grenzen für die Zeichentypen im Ascii-Code

const int8_t UC_LOWER_BORDER = 65;   //Großbuchstaben
const int8_t UC_HIGHER_BORDER = 90;
const int8_t LC_LOWER_BORDER = 97;   //Kleinbuchstaben
const int8_t LC_HIGHER_BORDER = 122;
const int8_t UC_LC_DISTANCE = 32;    //Wert der addiert werden muss, um einen Großbuchstaben
                                     //in einen Kleinbuchstaben umzuwandeln

int main(){

	int32_t length; //Länge des Substrings
	int32_t begin;  //Startindex des Substrings innerhalb des zu überprüfenden Strings
	int32_t i;

	char str[] = "Das ist ein String";

	longest_ascending_substring( str, &begin, &length );

	if( length > 0 ){
		printf( "längster aufsteigender Substring ist:\n");
		for(i = 0; i <= length - 1; ++i)
			printf( "%c", str[i + begin] );
		printf( "\n" );
	}
	else{
		printf("nix gefunden\n");
	}

}

void longest_ascending_substring( char str[], int32_t* begin, int32_t* length ){

	int32_t i;
	//Zwischenspeicher für den bisher größten Substrings
	int32_t max_begin;
	int32_t max_length;
	//Zwischenspeicher für den gerade untersuchten Substring	
	int32_t current_begin;  
	int32_t current_length;

	char cc; //current Character
	char nc; //next Character

	i = 0;
	max_begin = 0;
	max_length = 0;


	//besteht der String nur aus Sonderzeichen und/oder Ziffern?
	while( !is_lower_case_letter(to_lower_case(str[i])) ){
		if(str[i] == '\0'){
			*begin = -1;
			*length = 0;
			return ;
		}
		++i;
	}

	current_begin = i;
	current_length = 1;

	while( str[i + 1] != '\0' ){

		cc = to_lower_case(str[i]);
		nc = to_lower_case(str[i + 1]);
		// sind cc und nc beides Kleinbuchstaben, wird verglichen ob sie alphabetisch in richtiger Reihenfolge stehen
		// ansonsten wird ein neuer Substring untersucht
		if(is_lower_case_letter(cc) && is_lower_case_letter(nc)){
			if(nc >= cc){
				++current_length;
			}
			else{
				current_length = 1;
				current_begin = i + 1;
			}
		}
		else{			
			current_length = 1;
			current_begin = i + 1;
		}
		//ist der gerade untersuchte Substring länger als der bisher größte
		//wird der gerade untersuchte als bisher größter gespeichert
		if(current_length > max_length){
			max_length = current_length;
			max_begin = current_begin;
		}
		++i;	
	}
	//Rückgabe der Ergebnisse
	*begin = max_begin;
	*length = max_length;
}

char to_lower_case( char c ){
	//ist das eingegebene Zeichen ein Großbuchstabe, wird der entsprechende Kleinbuchstabe zurückgegeben
	if( c >= UC_LOWER_BORDER && c <= UC_HIGHER_BORDER )
		c += UC_LC_DISTANCE;
	return c;

}

bool is_lower_case_letter( char c ){
	//gibt false zurück, wenn es sich bei c um eine Ziffer,
	//einen Großbuchstaben, oder ein Sonderzeichen handelt
	return c >= LC_LOWER_BORDER && c <= LC_HIGHER_BORDER;

}
                

Lösung von: reeman :3 (TU Ilmenau)

bs = list(input("Bitte gib den Buchstabensalat ein: "))

results = []
while bs:
    i = 0
    while bs[:i] == sorted(bs[:i]) and i <= len(bs):
        i += 1
    i -= 1
    results.append(bs[:i])
    bs = bs[i:]

longest_string = "".join(max(results, key=len))

print("Der laengste alphabetisch geordnete Substring ist {}.".format(repr(longest_string)))

                

Lösung von: Karl Welzel ()

function searchAlphaSequence(str) {
   var seqs = [""];
   function search(pos, scout) {
      var theSub = "";
      if (scout <= str.length) {
         while (str.charCodeAt(scout+1) > str.charCodeAt(scout)) scout++;
         theSub = str.substring(pos, scout+1);
         if (theSub.length > seqs[0].length) 
            seqs = [theSub];
         else if (theSub.length == seqs[0].length)
            seqs.push(theSub);
         search(scout+1, scout+1);   
      }
   }
   search(0, 0);
   return seqs[0];
}

console.log(searchAlphaSequence(prompt("Buchstabensalat:")));
                

Lösung von: Lisa Salander (Heidi-Klum-Gymnasium Bottrop)

Aktionen

Bewertung

Durchschnittliche Bewertung:

Eigene Bewertung:
Bitte zuerst anmelden

Meta

Zeit: 1
Schwierigkeit: Leicht
Webcode: n5jh-p4n3
Autor: ()

Download PDF

Download ZIP

Zu Aufgabenblatt hinzufügen