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
11 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)
// NET 6.x | C# 10.x | VS-2022
IList<string> GetLongestAlphabetSequences(string t) {
var sb = new System.Text.StringBuilder();
var lst = new List<string>();
t = t.ToLower() + '\0';
for (int i = 0; i < t.Length - 1; i++) {
sb.Append(t[i]);
if (t[i + 1] <= t[i]) {
lst.Add(sb.ToString());
sb.Clear();
}
}
return lst.Where(x => x.Length == lst.Max(x => x.Length)).ToList();
}
var salat = new List<string> { "kotafgovlav", "abcbcd", "sakdeidpoidweoidowijk" };
salat.ForEach(x => Console.WriteLine(string.Join(", ", GetLongestAlphabetSequences(x))));
// afgov
// abc, bcd
// dei, dow, ijk
Lösung von: Jens Kelm (@JKooP)
// C++ 17
#include <iostream>
#include <vector>
#include <algorithm>
using s_t = std::string;
using v_t = std::vector<s_t>;
template <typename T, typename F>
void vector_iter(const std::vector<T>& vec, const F& fun) {
for (const auto& obj : vec) fun(obj);
}
s_t string_join(const v_t& vec, const s_t& sep) {
s_t str{};
vector_iter(vec, [&](auto e) { str += (e + sep); });
return str.substr(0, str.length() - sep.length());
}
v_t get_longest_alphabet_sequences(const s_t& str) {
v_t vec_tmp{}, vec_out{};
s_t str_tmp{}, str_t{ str };
std::transform(str_t.begin(), str_t.end(), str_t.begin(), ::tolower);
str_t += ' ';
auto max{ 0 };
for (size_t i{ 0 }; i < str_t.length() - 1; ++i) {
str_tmp.push_back(str_t[i]);
if (str_t[i + 1] <= str_t[i]) {
max = std::max(max, (int)str_tmp.length());
vec_tmp.push_back(str_tmp);
str_tmp.clear();
}
}
vector_iter(vec_tmp, [&](auto s) { if (s.length() == max )vec_out.push_back(s); });
return vec_out;
}
int main() {
v_t salat{ "kotafGovlav", "abcbcd", "sakdeidpoidweoidowijk" };
vector_iter(salat, [](auto str) {std::cout << string_join(get_longest_alphabet_sequences(str), ", ") << "\n"; });
}
// afgov
// abc, bcd
// dei, dow, ijk
Lösung von: Jens Kelm (@JKooP)
Aktionen
Neue Lösung hinzufügen
Bewertung
Durchschnittliche Bewertung:
Meta
Zeit: | 1 |
Schwierigkeit: | Leicht |
Webcode: | n5jh-p4n3 |
Autor: | () |
Kommentare (4)
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 ;-)
..ich denke beim else könnte man das if auch ganz weglassen.
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