สมมติว่าเรามีสตริงตัวพิมพ์เล็ก s เราต้องตรวจสอบว่าการเกิดขึ้นของตัวอักษรใน s หลังจากการจัดเรียงในลักษณะที่เป็นไปได้ใดๆ จะสร้างลำดับของ Recaman หรือไม่ (ละเว้นเทอมแรก)
ลำดับของ Recaman มีดังนี้ −
$$a_{n}=\begin{cases}\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:0(if\:n=0 ) &\\a_{n-1}-n(if\:a_{n}-n>0\wedge not\:present\in sequence) &\\\:\:\:\:\:\:\ :\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:a_{n-1}+n(มิฉะนั้น)\end{กรณี }$$
บางรายการของ Recaman's Sequence ได้แก่ [0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, 22, 10, 23, 9, 24,...] (เทอมแรกคือ ละเว้นเนื่องจากนี่คือ 0)
ดังนั้น หากอินพุตเป็น s ="pppuvuuqquuu" เอาต์พุตจะเป็น True เนื่องจากอักขระและความถี่คือ (p, 3), (u, 6), (v, 1) และ (q, 2) ดังนั้นความถี่จึงก่อตัวเป็นสองสามเทอมแรกของ Recaman's Sequence [1, 3, 6, 2]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- freq :=แผนที่ที่มีอักขระทั้งหมดเป็น s และความถี่
- n :=ขนาดของความถี่
- array :=first n เงื่อนไขลำดับของ Recaman
- f :=1
- สำหรับอักขระแต่ละตัวในความถี่ ให้ทำ
- is_found :=0
- สำหรับ j ในช่วง 1 ถึง n ทำ
- ถ้า freq[keys] เหมือนกับ array[j] แล้ว
- is_found :=1
- ออกมาจากวงจร
- ถ้า freq[keys] เหมือนกับ array[j] แล้ว
- ถ้า is_found เป็นเท็จ
- f :=0
- ออกมาจากวงจร
- คืนค่า True เมื่อตั้งค่า f เป็นเท็จ
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
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))
อินพุต
"pppuvuuqquuu"
ผลลัพธ์
True
