Weird Algorithm
Weird Algorithm
عند إعطائك عددًا صحيحًا موجبًا \(n\)، كرّر العمليات التالية:
- إذا كان \(n\) زوجيًا، اجعل \(n \leftarrow n/2\)؛
- إذا كان \(n\) فرديًا، اجعل \(n \leftarrow 3n+1\).
اطبع جميع قيم \(n\) ابتداءً من القيمة الأولية حتى يصل إلى \(1\).
الحل
نقوم بمحاكاة العملية بطريقة تكرارية. ابدأ بطباعة القيمة الأولية لـ \(n\)، ثم في كل خطوة حدّث \(n\) وفقًا لقاعدة الزوجي/الفردي واطبعها. من المفترض نظريًا أن تصل هذه السلسلة دائمًا إلى \(1\)، ويطلق عليها “مخمن كولاتز”؛ في هذه المسألة، نقوم فقط بمحاكاة العملية حتى يصبح \(n=1\).
تلميحمحاكاة باستخدام حلقة
حلقة while واحدة تكفي: اطبع، حدّث \(n\)، وتوقف عند الوصول إلى \(n=1\).
#include <iostream>
using namespace std;
int main() {
long long n;
cin >> n;
cout << n;
while (n != 1) {
if (n % 2 == 0) {
n /= 2;
} else {
n = 3*n + 1;
}
cout << ' ' << n;
}
}
تنبيهتجاوز السعةOverflow
على الرغم من أن الإدخال يحقق \(1 \le n \le 10^6\)، فإن القيم الوسيطة في السلسلة يمكن أن تتجاوز \(10^9\). استخدم long long لتجنب تجاوز السعة أثناء حساب \(3*n+1\).