x = b * (s(x)^a) + c
مدخلات البرنامج هي a, b, c
والمطلوب ايجاد جميع حلول المعادلة من واحد الى 10 قوة تسعة
حيث ان التابع s يقوم بجمع خانات الرقم مثلا 123 مجموع خاناته 6 و 1234 مجموع خاناته 10
هل يمكنك حل هذه المعادلة برمجياً ؟
x = b * (s(x)^a) + c
أظن أن في المعادلة السابقة خطأً، فكيف لنا أن نحل معادلة بهذا الشكل مثلًا:
س = س×2
حيث لا يمكننا أن نحدد قيمة س من الأساس.
أجل المطلوب إيجاد x التي تحقق المعادلة
مثال
x = 33*s(x)^1+45
من بين حلولها
x = 342
s(x) = 9
33*s(x)^1+45 = 33*9+45 = 342 = x
function s(x) {
"use strict";
var i = 0, S = 0;
x = x.toString();
while (i < x.length) {
S += Number(x[i]);
i += 1;
}
return S;
}
function mo3adala(a, b, c, lim) {
"use strict";
var x = 0, t;
while (true) {
t = b * Math.pow(s(x), a) - c;
if (t === x) {
return x;
} else if (x > lim) {
return false;
}
x += 1;
}
}
كود JavaScript الدالة هي
mo3adala(a, b, c, lim);
حيث:
lim هي الحد الذي عنده الدالة تتوقف إن لم تجد حلا وتعيد false
(a,b,c) أعداد موجبة
فكرت قليلا هل من إمكانية لحلها رياضيا فلم أجد
ثم شرعت في الحل برمجيالم تكن لدي المشكلة في الفكرة
أخدت الوقت فقط في تشغيل المحرر و كتابة الأكواد
شكراً لك على المشاركة لكن من دون ان تنزعج من لا تفرح كثيراً يا صديقي رغم ان حلك صحيح لكنه في عالم البرمجيات فاشل :]
احزر لماذا ؟
لانك مشيت بتعقيد 10 مليار
اي انك اجريت هذا الاختبار على 10 مليار رقم وهذا تسبب في توقف متصفحي لبرهة
حللتها انا بتعقيد 81 اي انني اجريت الاختبار على 81 رقم فقط :]
ان لم ترد التفكير في كيفية فعل هذا سأنشر حلي
هل يمكنك أن تشرح لي الخوارزمية التي إستعملت
لا أعرف كيف أشغل هذا الكود
وحسب ما فهمت فالكود يجري الإختبار على الأعداد الأصغر من 81
انظر الى المعادلة فوق
خذ s الطرفين (كما تأخذ لوغارتم الطرفين)
وبما ان جميع مدخلاتنا تحت عشرة قوة تسعة اي أن اكبر رقم فيهم هو 999999999 ومجموع ارقامه 81
بالتالي s(x) محصور بين 1 و 81
وعندما تأخذ s الطرفين يبقى ان توجد قيمة الطرف الايمن للمعادلة وتقارنه s هذا الطرف مع الطرف الايسر .. وان كانا متساووين يكون هذا احد الحلول
فهمت الآن
في كل مرة يتم إعطاء قيمة ل s
تم يتم حساب b * (s^a) + c
وإذا كان مجموع أرقامه يساوي s يكون حلا
- خوارزمية رائعة بالتوفيق :)
ليست خوارزميتي -_-
حللتها مثلك اول شيء ولم تأخذ وقتاً ابداً
لكن عندما رفعتها على موقع التحقق من الكود قال لي انني استهلكت وقتاً كثيراً واعطاني خطأ في الكود
ظللت يومين افكر في قانون رياضي يأتي لي بهذه الارقام ثم اليوم قرات اننا يجب ان نأخذ s الطرفين وطبقته على الكود
لكن تطبيقه اخذ ساعتين لان الفكرة كانت صعبة قليلاً وخاصة ان انكليزيته كانت ركيكة جداً فهو روسي
codeforces.com
سجل بالموقع هذا وادخل الى problem set واضغط على كلمة solved كي تترتب المسائل بحسب كم شخص قام بحلها
قم بحل مسائل div2. A و div2. B
لان ما فوق ذلك صعب ويحتاج خوارزميات معينة
الموقع يعمل على كثير من اللغات لكن يجب الانتباه لطريقة الدخل والخرج فان كان في خرجك مسافة زائدة ستأخذ wrong answer
الحل سهل استعمال binary search عوض linear search
(لا يعمل الا اذا كانت ال function monotone وهذه حالتنا) لا أعرف monotone بالعربي أو الانجليزي ولكن يعني أن
لكل x و k اذا كان x>k فان f(x)>f(k) أو العكس f(x)<f(k) (ماهي الكلمة أرجوكم أدرس الرياضيات بالفرنسية ,,,)
بالنسبة للتعقيد هو O(log(n))
هنا عندما أكتب log يعني base 2
اذا ال Upper bound هو log(10^9)
يعني تقريبا سيقوم ب 30 عملية الى أن يصل الى الحل الصحيح عوض مليار في حالة linear search
مونوتون اعتقد تعني ان مشتقها لا ينعدم .. اي الدالة اما متزايدة تماماً او منتاقصة تماماً
وبمعنى آخر فإن المستقر الفعلي لها مرتب
لا اعتقد ابداً ان الباينري سيرش صالحة .. لم افهم فكرتك لماذا لا تقوم بتكويدها ؟
وكيف عرفت أن الإختبار أجري فقط على 81 رقم
بالنسبة للدالة التي قدمتها تتوقف بمجرد أن تجد حلا وبذلك تكون قد أجرت x إختبار
وإن لم يكن هناك أي حل تكون قد أجرت lim إختبار
نعم صحيح لم أفكر فيها في الصباح لم أخذ قهوتي وأدويتي
- اسف لن تعمل ال bs لان S(x) ليست monotone
هو تطبيق صغير لل point fixe لا اعرف الاسم بالعربي أو الانجليزية
اه أشعر بالاحراج
برنامج ببايثون
a = 1
b = 33
c = 45
f = lambda x : x**a * b +c
for i in range(1, 82):
k = f(i)
if (k == f(sum(map( int, list(str(k)))))):
print k
ال upper bound هي 81 كما أشرت أنت لان
S(10^9-1) = 81
function s(x) {
"use strict";
var i = 0, S = 0;
x = x.toString();
while (i < x.length) {
S += Number(x[i]);
i += 1;
}
return S;
}
function mo3adala(a, b, c, lim) {
"use strict";
var x = 0, t, S = [];
while (true) {
t = b * Math.pow(s(x), a) - c;
if (t === x) {
S[S.length] = x;
} else if (x > lim) {
return S;
}
x += 1;
}
}
أو هذا الكود الذي يعطي الحلول x الأصغر من lim
function s(x) {
"use strict";
var i = 0, S = 0;
x = x.toString();
while (i < x.length) {
S += Number(x[i]);
i += 1;
}
return S;
}
function mo3adala(a, b, c) {
"use strict";
var S = 0, t, x = [];
while (S <= 81) {
t = b * Math.pow(S, a) + c;
if (S === s(t) && t <= 999999999) {
x[x.length] = t;
}
S += 1;
}
return x;
}
تطبيق الخوارزمية ب JavaScript
mo3adala(a, b, c);
تفضل الحل
def method(a, b, c)
for x in 1..1000000000
s = ((x*(x+1)) / 2) #Gauss_sum
t = (b * (s ** a)) + c
end
end
اعتذر يبدو انني فهمتها بشكل خطأ
التعليقات