Kiểm tra xem tần số của các ký tự có trong Chuỗi Recaman bằng Python hay không

Giả sử chúng ta có một chuỗi chữ thường s. Chúng tôi phải kiểm tra xem liệu sự xuất hiện của các bảng chữ cái theo s, sau khi sắp xếp lại theo bất kỳ cách nào có thể, tạo ra Trình tự của Recaman (bỏ qua số hạng đầu tiên).

Trình tự của Recaman như sau -

$$ a_ {n} =\ begin {case} \:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:0 (nếu \:n =0 ) &\\ a_ {n-1} -n (nếu \:a_ {n} -n> 0 \ nêm không \:hiện tại \ theo trình tự) &\\\:\:\:\:\:\:\ :\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:a_ {n-1} + n (nếu không) \ end {trường hợp } $$

Một số mục của Trình tự Recaman là [0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, 22, 10, 23, 9, 24, ...] (Số hạng đầu tiên là bị bỏ qua vì đây là 0)

Vì vậy, nếu đầu vào là s =​​"pppuvuuqquuu", thì đầu ra sẽ là True vì các ký tự và tần số là (p, 3), (u, 6), (v, 1) và (q, 2). Vì vậy, các tần số đang hình thành một vài số hạng đầu tiên của Trình tự Recaman [1, 3, 6, 2].

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• freq:=một bản đồ chứa tất cả các ký tự ở s và tần số của chúng
• n:=kích thước của freq
• array:=n số hạng thứ tự đầu tiên của Recaman
• f:=1
• đối với mỗi ký tự trong freq, hãy thực hiện
  • is_found:=0
  • đối với j trong phạm vi từ 1 đến n, thực hiện
    • nếu freq [phím] giống với mảng [j], thì
      • is_found:=1
      • ra khỏi vòng lặp
  • nếu is_found là false, thì
    • f:=0
    • ra khỏi vòng lặp
• trả về True khi f được đặt ngược lại là False

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

from collections import defaultdict
def recaman(array, n) :
   array[0] = 0
   for i in range(1, n + 1):
      temp = array[i - 1] - i
      for j in range(i):
         if array[j] == temp or temp < 0:
            temp = array[i - 1] + i
            break
      array[i] = temp
def solve(s) :
   freq = defaultdict(int)
   for i in range(len(s)) :
      freq[s[i]] += 1
   n = len(freq)
   array = [0] * (n + 1)
   recaman(array, n)
   f = 1
   for keys in freq.keys() :
      is_found = 0
      for j in range(1, n + 1) :
         if freq[keys] == array[j]:
            is_found = 1
            break;
      if not is_found:
         f = 0
         break
   return True if f else False
s = "pppuvuuqquuu"
print(solve(s))

Đầu vào

"pppuvuuqquuu"

Đầu ra

True