Python Intro @ EdX.org

[mahoney85]

Hallo Leute,

ich mache gerade den Pyhton-Einführungskurs auf der EdX.org Seite und bin schon bei den ersten Hausaufgaben überfordert. Ich kann die Befehle noch nicht ganz einschätzen, z.B. wenn man einen 'if' Befehl in einen 'for'-Loop einbaut weiss ich nicht was genau wie durchlaufen wird ... Hier sind 2 Fragen, an denen ich schon seit Stunden sitze:

a) Assume s is a string of lower case characters.
Write a program that prints the number of times the string 'bob' occurs in s. For example, if s = 'azcbobobegghakl', then your program should print "The number of times 'bob' occurs is: 2"

Hier würde ich mit einem 'for'-loop und einem String Befehl rangehen ... aber ich hab keine Ahnung wie.
b) Assume s is a string of lower case characters.

Write a program that prints the longest substring of s in which the letters occur in alphabetical order. For example, if s = 'azcbobobegghakl', then your program should print. "The alphabetical order is: eggh"

Hier habe ich gar keine Ahnung.

Kann mir jemand vielleicht ein paar Hinweise geben bzw. Tipps geben, wo ich was dazu im Netz finde oder wie das, wonach ich suchen musst, heisst?

Vielen Dank!

M.

[Sirius3]

@mahoney85: die Aufgaben hören sich mehr danach an, als ob man reguläre Ausdrücke üben müßte:

Code: Alles auswählen

import re
s = 'azcbobobegghakl'
print(len(re.findall('(?=bob)', s)))
print(max(re.findall('a*b*c*d*e*f*g*h*i*j*k*l*m*n*o*p*q*r*s*t*u*v*w*x*y*z*', s), key=len))

Jetzt mal ernsthaft: wenn Du ein Problem nicht lösen kannst, dann teile es in Teilprobleme auf, von denen Du die Lösung kennst. Also bei a) wären das, erstmal einen String zu durchlaufen und immer 3 aufeinanderfolgende Zeichen zu extrahieren. Was Du dazu brauchst, hast Du sicher in den Kursunterlagen schon gelernt: eine for-Schleife über einen range von 0 bis zur Länge des Strings und String-Slicing s[i:i+3]. Als nächsten Schritt kannst Du diese Teilstrings mit "bob" vergleichen und bei Gleichheit einen Zähler um 1 hochzählen.

[BlackJack]

Eine Lösung für Teil a) die für beliebige (endliche) iterierbare Objekte funktioniert:

Code: Alles auswählen

from collections import deque


def count_possibly_overlapping_subsequence(iterable, needle):
    result = 0
    needle = deque(needle)
    queue = deque([], len(needle))
    for item in iterable:
        queue.append(item)
        if queue == needle:
            result += 1
    return result

[BlackJack]

In C könnte man das so lösen (getestet auf einem C64 ):
[codebox=c file=Unbenannt.c]#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>


unsigned int count_possibly_overlapping_substring(char *haystack, char *needle)
{
unsigned int result = 0;
size_t needle_length = strlen(needle);

for ( ; *haystack; ++haystack) {
if (strncmp(haystack, needle, needle_length) == 0) ++result;
}
return result;
}


char* get_longest_non_decreasing_substring(char *string)
{
unsigned int i, j, k, max_length, length;
char *result;

i = k = max_length = 0;
while (string) {
j = i;
while (((uint8_t) string[j]) <= ((uint8_t) string[j + 1])) ++j;
length = j - i + 1;
if (length > max_length) {
max_length = length;
k = i;
}
i = j + 1;
}
result = malloc(max_length + 1);
if (result) {
memcpy(result, string + k, max_length);
result[max_length] = '\0';
}
return result;
}


int main(void) {
char *string = "azcbobobegghakl";
char *needle = "bob";
char *substring;

printf(
"The number of times '%s' occurs is: %d\n",
needle,
count_possibly_overlapping_substring(string, needle)
);

substring = get_longest_non_decreasing_substring(string);
if (substring) {
printf("The alphabetical order is: %s\n", substring);
free(substring);
} else {
puts("Out of memory.");
}

return 0;
}[/code]

[BlackJack]

Eine Lösung für a) und b) mit LISP-Flavour:

Code: Alles auswählen

#!/usr/bin/env hy
(require [hy.contrib.loop [loop]])
 
 
(defn count-possibly-overlapping-substring [string needle]
  (let [length (len needle)]
    (sum
      (genexpr
        (= (cut string i (+ i length)) needle)
        [i (range (len string))]))))
 
 
(defn get-longest-non-decreasing-substring [string]
  (loop [[string string] [current '()] [longest '()]]
    (if (empty? string)
      (.join "" (reversed (max current longest :key len)))
      (let [character (car string)
            remainder (cdr string)]
        (if (and (not (empty? current)) (> (car current) character))
          (recur remainder (cons character None) current)
          (recur remainder (cons character current) longest))))))
 
 
(defmain [&rest args]
  (let [string "azcbobobegghakl"
        needle "bob"]
    (print
      (.format "The number of times '{0}' occurs is: {1}"
        needle
        (count-possibly-overlapping-substring string needle)))
    (print
      (.format "The alphabetical order is: {0}"
        (get-longest-non-decreasing-substring string)))))