אלגוריתם: האם מכשפה?

אלגוריתם האם_מכשפה? (אישה) הוא אלגוריתם אשר פותח על ידי האינקוויזיציה הקדושה בימי הביניים, בזמן צייד המכשפות. האלגוריתם מקבל אישה ומחזיר "אמת" אם היא מכשפה, אחרת מחזיר "שקר". הנחות: האישה חיה.

הגרסה הרקורסיבית

1) שאל את האישה "האם את מכשפה?" וזכור את התשובה

2) אם (התשובה="כן") אזי

2.1) החזר "אמת"

3) אחרת

3.1) תן מכה לאישה

3.2) הפעל אלגוריתם האם_מכשפה?(אישה)

אלגוריתם יעיל יותר

מכיוון שאין כל חסם על זמן הריצה של האלגוריתם המקורי (כי למי שמריץ אותו עלולה לכאוב היד), האינקויזציה החליטה לפתח אלגוריתם יעיל יותר, שעובד בזמן קבוע. להלן האלגוריתם:

1) העלה את האישה על המוקד

2) הדלק את המוקד

3) אם האישה נשרפה אזי

3.1) החזר "שקר"

4) אחרת

4.1) החזר "אמת"

אלגוריתם נוסף

אלגוריתם שנוסה בהצלחה ע"י הפיתון של מונטי, צוות פיתוח מיוחד שהוקם לצורך בדיקת אלגוריתמים משופרים. במידה ואין בנמצא חומרי בעירה, אבל יש אגם. הנחות היסוד : מכיוון שברור שעץ בוער וגם מכשפות (אלגוריתם קודם). עץ וגם ברווזים צפים על מים. אזי, אם היא מכשפה, היא מעץ ולכן תשקול כמו ברווז, מסקנה - המכשפה תצוף.

1) קשור לאישה אבנים גדולות לרגליים (זה בכדי שהאלגוריתם לא יזוז).

2) זרוק את האישה לאגם.

3) אם האישה צפה

3.1) החזר "אמת"

4) אחרת

4.1) החזר "שקר"

עוד אלגוריתם נוסף

הוכח כי אלגוריתם זה הוא הכי פחות יעיל וגורם לכאבי הראש החמורים ביותר מכל הארבעה:

1)העלה את החשודה על המוקד ושרוף אותה.

2)אם האישה נשרפת אזי:

2.1)היא אינה מכשפה, התנצל ועזוב אותה לנפשה.

3)אחרת

3.1)היא מכשפה! יש לשרוף אותה מייד! העלה אותה על המוקד ושרוף אותה.

4)בזמן שאתה צופה במכשפה נשרפת, דפוק לעצמך לוח עץ עבה וחזק בראש עד שייגרמו לך כאבי הראש החמורים ביותר מכל הארבעה.