المحيط بهذا البرنامج لتحديد مجموع الأعداد الصحيحة المتبادلة التي لا تحتوي على صفر
https://stackoverflow.com/questions/3847615
-
27-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
يترك أ تشير إلى مجموعة الأعداد الصحيحة الإيجابية التي لا تحتوي تمثيلها العشري على الرقم 0. مجموع المعاملة بالمثل للعناصر في أ من المعروف أن 23.10345.
السابق. 1،2،3،4،5،6،7،8،111-19،21-29،31-39،41-49،51-59،61-69،71-79،81-89 ، 91-99،111-119 ، ...
ثم خذ المتبادل لكل رقم ، وتجمل المجموع.
كيف يمكن التحقق من ذلك عدديًا؟
اكتب برنامج كمبيوتر للتحقق من هذا الرقم.
هذا ما كتبته حتى الآن ، أحتاج إلى مساعدة المحيط هذه المشكلة لأن هذا يستغرق وقتًا طويلاً جدًا لإكماله:
رمز في جافا
import java.util.*;
public class recip
{
public static void main(String[] args)
{
int current = 0; double total = 0;
while(total < 23.10245)
{
if(Integer.toString(current).contains("0"))
{
current++;
}
else
{
total = total + (1/(double)current);
current++;
}
System.out.println("Total: " + total);
}
}
}
المحلول
هذا ليس بهذه الصعوبة عند الاقتراب بشكل صحيح.
افترض على سبيل المثال أنك تريد العثور على مجموع المعاملة المتبادلة من جميع الأعداد الصحيحة التي تبدأ (أي أرقام أكثر اليسار) مع 123 وينتهي بأرقام K غير صفرية. من الواضح أن هناك 9ك مثل هذه الأعداد الصحيحة والمتبادل لكل من هذه الأعداد الصحيحة في النطاق 1/(124*10ك) .. 1/(123*10ك). وبالتالي فإن مجموع المعاملة بالمثل من كل هذه الأعداد الصحيحة يحدها (9/10)ك/124 و (9/10)ك/123.
لإيجاد حدود لمجموع جميع المعاملات المتبادلة التي تبدأ بـ 123 ، يتعين على واحد إضافة الحدود أعلاه لكل k> = 0. هذه دولة هندسية ، وبالتالي يمكن اشتقاقها أن مجموع المعاملين من الأعداد الصحيحة التي تبدأ بـ 123 يحدها 10*(9/10)ك/124 و 10*(9/10)ك/123.
بالطبع يمكن تطبيق نفس الطريقة للحصول على أي مجموعة من أرقام اليسار. كلما زاد عدد الأرقام التي نفحصها على اليسار ، كلما أصبحت النتيجة أكثر دقة. فيما يلي تنفيذ هذا النهج في بيثون:
def approx(t,k):
"""Returns a lower bound and an upper bound on the sum of reciprocals of
positive integers starting with t not containing 0 in its decimal
representation.
k is the recursion depth of the search, i.e. we append k more digits
to t, before approximating the sum. A larger k gives more accurate
results, but takes longer."""
if k == 0:
return 10.0/(t+1), 10.0/t
else:
if t > 0:
low, up = 1.0/t, 1.0/t
else:
low, up = 0, 0
for i in range(10*t+1, 10*t+10):
l,u = approx(i, k-1)
low += l
up += u
return low, up
استدعاء تقريبا (0 ، 8) على سبيل المثال يعطي الحد الأدنى والأعلى: 23.103447707 ... و 23.103448107 .... وهو قريب من المطالبة 23.10345 المقدمة من المرجع.
هناك طرق تتقارب بشكل أسرع إلى المبلغ المعني ، لكنها تتطلب المزيد من الرياضيات. يمكن العثور على تقريب أفضل بكثير للمبلغ هنا. تعميم المشكلة هو سلسلة Kempner.
نصائح أخرى
لجميع قيم current أكبر من بعض العتبة N, 1.0/(double)current سيكون ذلك صغيرًا بما فيه الكفاية total لا يزداد نتيجة للإضافة 1.0/(double)current. وبالتالي ، يجب أن يكون معيار الإنهاء مثل
while(total != total + (1.0/(double)current))
بدلاً من الاختبار مقابل الحد المعروف مسبق. ستتوقف حلقتك عندما current يصل إلى هذه القيمة الخاصة لـ N.
أظن أن الصب إلى سلسلة ثم التحقق من الحرف "0" هي الخطوة التي تستغرق وقتًا طويلاً. إذا كنت ترغب في تجنب جميع الأصفار ، فقد يساعد في الزيادة current هكذا:
(تم تحريره - بفضل آرون مكسموث)
current++;
for( int i = 10000000; i >= 10; i = i / 10 )
{
if ( current % i ) == 0
{
current = current + ( i / 10 );
}
}
هذا لم يخبره ، ولكن يجب أن يكون المفهوم واضحًا: كلما وصلت إلى مضاعف قوة من عشرة (على سبيل المثال 300 أو 20000) ، يمكنك إضافة الطاقة السفلية التالية 10 (في أمثلةنا 10 + 1 و 1000 + 100 + 10 + 1 ، على التوالي) حتى لا يكون هناك مزيد من الأصفار في رقمك.
تغيير الخاص بك while وفقًا لذلك ، ومعرفة ما إذا كان هذا لا يساعد في الأداء إلى هذه النقطة ، أصبحت مشكلتك قابلة للإدارة.
أوه ، وقد ترغب في تقييد System.out الإخراج قليلا كذلك. هل سيكون كل التكرار العاشر أو التكرار 10000 كافٍ؟
تحرير الثاني:بعد بعض النوم ، أظن أن إجابتي قد تكون قصيرة النظر قليلاً (إلقاء اللوم على الساعة المتأخرة ، إذا صح التعبير). كنت آمل ببساطة ذلك ، أوه ، مليون تكرار current سوف تنقلك إلى الحل وتركه في ذلك ، بدلاً من حساب حالات التصحيح باستخدام log( current ) إلخ.
في الفكر الثاني ، أرى مشكلتين مع هذه المشكلة برمتها. الأول هو أن رقم 23.10345 هو leeeeettle لتدور لأذواقي. بعد كل شيء ، أنت تضيف آلاف العناصر مثل "1/17" و "1/11111" وما إلى ذلك ، مع تمثيلات عشرية لا حصر لها ، ومن غير المرجح أن تضيف ما يصل إلى 23.10345 بالضبط. إذا كان بعض المتخصصين في الرياضيات العددية يقول ذلك ، فلا بأس - ولكن بعد ذلك أود أن أرى الخوارزمية التي وصلت بها إلى هذا الاستنتاج.
ترتبط المشكلة الأخرى بالأول وتتعلق بالذاكرة المحدودة الثنائية تمثيل أرقامك العقلانية. قد تحصل على استخدام bigdecimals, ، لكن لدي شكوكي.
لذلك ، في الأساس ، أقترح عليك إعادة برمجة الخوارزمية العددية بدلاً من الذهاب إلى حل القوة الغاشمة. آسف.
تحرير الثالث:بدافع الفضول ، كتبت هذا في C ++ لاختبار نظرياتي. يتم تشغيله لمدة 6 دقائق الآن وهو في حوالي 14.5 (حوالي 550 ميو. التكرارات). سوف نرى.
الإصدار الحالي هو
double total = 0;
long long current = 0, currPowerCeiling = 10, iteration = 0;
while( total < 23.01245 )
{
current++;
iteration++;
if( current >= currPowerCeiling )
currPowerCeiling *= 10;
for( long long power = currPowerCeiling; power >= 10; power = power / 10 )
{
if( ( current % power ) == 0 )
{
current = current + ( power / 10 );
}
}
total += ( 1.0 / current );
if( ! ( iteration % 1000000 ) )
std::cout << iteration / 1000000 << " Mio iterations: " << current << "\t -> " << total << std::endl;
}
std::cout << current << "\t" << total << std::endl;
حساب currPowerCeiling (أو مع ذلك يمكن للمرء أن يسمي هذا) باليد يحفظ بعض log10 و pow الحسابات كل تكرار. كل شيء يساعد - لكنه لا يزال يستغرق إلى الأبد ...
تحرير الرابع:تبلغ حوالي 66000 تكرار Mio ، ويبلغ إجمالي ما يصل إلى 16.2583 ، ويبلغ وقت التشغيل حوالي 13 ساعة. لا تبدو جيدة ، بوبي س - أقترح نهجًا أكثر رياضية.
ماذا عن تخزين الرقم الحالي كبايت حيث يكون كل عنصر صفيف رقمًا 0-9؟ وبهذه الطريقة ، يمكنك اكتشاف الأصفار بسرعة كبيرة (مقارنة البايتات باستخدام == بدلاً من String.contains).
الجانب السلبي هو أنك ستحتاج إلى تنفيذ زيادة نفسك بدلاً من الاستخدام ++. ستحتاج أيضًا إلى وضع طريقة لتمييز أرقام "غير موجودة" حتى لا تكتشفها كأصفار. تخزين -1 بالنسبة للأرقام غير الموجودة يبدو وكأنه حل معقول.
للحصول على عدد صحيح موقّع 32 بت ، لن يتوقف هذا البرنامج أبدًا. سوف تتقارب في الواقع نحو -2097156. نظرًا لأن الحد الأقصى للرقم التوافقي (مجموع المتبادلون المتكامل من 1 إلى ن) من عدد صحيح موقّع 32 بت هو ~14.66, ، لن تنتهي هذه الحلقة أبدًا ، حتى عندما تتفوق التيار من 2^31 - 1 ل -2^31. نظرًا لأن المتبادل لأكبر عدد صحيح سلبي 32 بت هو ~ -4.6566e-10 ، في كل مرة يعود فيها الحالي إلى 0, ، سيكون المبلغ سلبيا. بالنظر إلى أن أكبر عدد ممثل من قبل أ double مثل ذلك number + + 1/2^31 == number هو 2^52/2^31, ، تحصل تقريبا -2097156 كقيمة متقاربة.
بعد قولي هذا ، وافتراض أنه ليس لديك طريقة مباشرة لحساب العدد التوافقي من عدد صحيح تعسفي ، هناك بعض الأشياء التي يمكنك القيام بها لتسريع حلقة الداخلية الخاصة بك. أولاً ، ستكون أغلى عملية System.out.println; ؛ يجب أن يتفاعل ذلك مع وحدة التحكم في هذه الحالة ، سيتعين على برنامجك في النهاية مسح المخزن المؤقت إلى وحدة التحكم (إن وجدت). هناك حالات قد لا يحدث فيها ذلك بالفعل ، ولكن نظرًا لأنك تستخدم ذلك لتصحيح الأخطاء ، فهي ليست ذات صلة بهذا السؤال.
ومع ذلك ، فأنت تقضي أيضًا الكثير من الوقت في تحديد ما إذا كان الرقم لديه صفر. يمكنك أن تقلب هذا الاختبار لتوليد نطاقات من الأعداد الصحيحة بحيث يكون لديك ضمن هذا النطاق لعدم وجود عدد صحيح برقم صفر. هذا أمر بسيط حقًا في القيام به بشكل تدريجي (في C ++ ، ولكن تافهة بما يكفي للتحويل إلى Java):
class c_advance_to_next_non_zero_decimal
{
public:
c_advance_to_next_non_zero_decimal(): next(0), max_set_digit_index(0)
{
std::fill_n(digits, digit_count, 0);
return;
}
int advance_to_next_non_zero_decimal()
{
assert((next % 10) == 0);
int offset= 1;
digits[0]+= 1;
for (int digit_index= 1, digit_value= 10; digit_index<=max_set_digit_index; ++digit_index, digit_value*= 10)
{
if (digits[digit_index]==0)
{
digits[digit_index]= 1;
offset+= digit_value;
}
}
next+= offset;
return next;
}
int advance_to_next_zero_decimal()
{
assert((next % 10)!=0);
assert(digits[0]==(next % 10));
int offset= 10 - digits[0];
digits[0]+= offset;
assert(digits[0]==10);
// propagate carries forward
for (int digit_index= 0; digits[digit_index]==10 && digit_index<digit_count; ++digit_index)
{
digits[digit_index]= 0;
digits[digit_index + 1]+= 1;
max_set_digit_index= max(digit_index + 1, max_set_digit_index);
}
next+= offset;
return next;
}
private:
int next;
static const size_t digit_count= 10; // log10(2**31)
int max_set_digit_index;
int digits[digit_count];
};
ما يفعله الرمز أعلاه هو التكرار على كل مجموعة من الأرقام بحيث لا يحتوي النطاق إلا على أرقام بدون أصفار. يعمل عن طريق تحديد كيفية الانتقال من N000 ... إلى N111 ... ومن N111 ... إلى (n+1) 000 ... ، يحمل (n+1) إلى 1 (0) 000 ... إذا من الضروري.
على جهاز الكمبيوتر المحمول الخاص بي ، يمكنني إنشاء العدد التوافقي من 2^31 - 1 في 8.73226 ثانية.
public class SumOfReciprocalWithoutZero {
public static void main(String[] args) {
int maxSize=Integer.MAX_VALUE/10;
long time=-System.currentTimeMillis();
BitSet b=new BitSet(maxSize);
setNumbersWithZeros(10,maxSize,b);
double sum=0.0;
for(int i=1;i<maxSize;i++)
{
if(!b.get(i))
{
sum+=1.0d/(double)i;
}
}
time+=System.currentTimeMillis();
System.out.println("Total: "+sum+"\nTimeTaken : "+time+" ms");
}
static void setNumbersWithZeros(int srt,int end,BitSet b)
{
for(int j=srt;j<end;j*=10)
{
for(int i=1;i<=10;i++)
{
int num=j*i;
b.set(num);
}
if(j>=100)
setInbetween(j, b);
}
}
static void setInbetween(int strt,BitSet b)
{
int bitToSet;
bitToSet=strt;
for(int i=1;i<=10;i++)
{
int nxtInt=-1;
while((nxtInt=b.nextSetBit(nxtInt+1))!=strt)
{
b.set(bitToSet+nxtInt);
}
nxtInt=-1;
int lim=strt/10;
while((nxtInt=b.nextClearBit(nxtInt+1))<lim)
{
b.set(bitToSet+nxtInt);
}
bitToSet=strt*i;
}
}
}
هذا تطبيق باستخدام bitset.i حسبت مجموع المعاملة بالمثل لجميع عدد صحيح في النطاق (1-Integer.MAX_VALUE/10). يأتي المبلغ 13.722766931560747هذا هو الحد الأقصى الذي يمكنني حسابه باستخدام bitset لأن الحد الأقصى للمدى للبوتست هو عدد صحيح. الكود داخل الحالة قد يمنحك فكرة جديدة لتحسين التعليمات البرمجية الخاصة بك. (قم بزيادة ذاكرتك باستخدام وسيطة VM -Xmx[Size>350]m)
انتاج:
Total: 13.722766931560747
TimeTaken : 60382 ms
تحديث:
تنقل جافا من الإجابة السابقة المحذوفة:
public static void main(String[] args) {
long current =11;
double tot=1 + 1.0/2 + 1.0/3 + 1.0/4 + 1.0/5 + 1.0/6 + 1.0/7 + 1.0/8 + 1.0/9;
long i=0;
while(true)
{
current=next_current(current);
if(i%10000!=0)
System.out.println(i+" "+current+" "+tot);
for(int j=0;j<9;j++)
{
tot+=(1.0/current + 1.0/(current + 1) + 1.0/(current + 2) + 1.0/(current + 3) + 1.0/(current + 4) +
1.0/(current + 5) + 1.0/(current + 6) + 1.0/(current + 7) + 1.0/(current + 8));
current += 10;
}
i++;
}
}
static long next_current(long n){
long m=(long)Math.pow(10,(int)Math.log10(n));
boolean found_zero=false;
while(m>=1)
{
if(found_zero)
n+=m;
else if((n/m)%10==0)
{
n=n-(n%m)+m;
found_zero=true;
}
m=m/10;
}
return n;
}
