مسألة برمجية للتدريب (تحتاج معرفة Binary)

خوازميتي

lowerbound, upperbound = map(int, raw_input().split())
c = 0
for i in range(len(bin(lowerbound))-2, len(bin(upperbound))-1):
    s = ['1'] * i
    for j in range(len(s)-1):
        k = s[:]
        k[len(k)-1-j] = '0'
        k = int(''.join(k), 2)
        if (k<=upperbound) and (k>=lowerbound):
            c += 1
print c

تعمل على الامثلة التي أدخلتها 

لا أعرف ان كانت الحل الافضل ولكن هذا أفضل ماأستطيع التفكير فيه حاليا.

أظن أن الخوارزمية سريعة كفاية (ان لم اخطئ في حساب التعقيد)

   O(log2(m)^2)

أيضا شكرا على التمارين الجيدة.

يبدو ان هناك احد قد **** من هذه المسألة ولم يعرف الحل فقام بالتسليب ههه

لا اعلم لم اخذ تسليبات دائماً على هذه المسائل هل انت سبامر ؟

ان لم تكن ارجوك قل لي السبب

مُحاولتي:

def count_valid_numbers(n, m):
    valid_num = 0
    while n <= m:
        count_zeros = bin(n)[2:].count('0')
        if count_zeros == 1:
           valid_num += 1
        n += 1
    return valid_num

جرّبت الشيفرة على المثالين الأول والثاني فقط، وكانت النّتيجة صحيحة. بالنّسبة للمثال الأخير فلا أظنّ أنّه سينتهي إلا بعد بضعة سويعات :(

@محمد عزيز الكناني الشيفرة الخاصّة بك طويلة نوعا ما، وهل جرّبتها مع المثال الأخير؟ قُمت بتجربتها منذ مدّة ولا زالت قيد التّنفيذ إلى الآن، أعتقد بأنّ سُرعتا الدّالتين مُتشابهتان.

@Rashadoo هل لك بأن توفر بعض الأمثلة الأخرى لأجرّب بها خوارزميّتي؟

هل تريد حلا يقوم ب m-n عملية :)

هذه المرة قد لا يخرج المتصفح من حلقة التكرار ههه

 public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String a = sc.nextLine();
     String b = sc.nextLine();
     int count=0;
     int zeroCount=0;
      String binary="";
      char[] binaryChar=null;
      boolean bool=true;
      int j=0;
      long aa = Long.parseLong(a);
      long bb = Long.parseLong(b);
      long i = aa;
      while(i<=bb){
         binary = Long.toBinaryString(i);
          binaryChar = binary.toCharArray();
            int len = binary.length();
            while (bool & j!=len){
                if (binaryChar[j]=='0'){
                    zeroCount++;
                }
                if (zeroCount>1){
                 bool=false;
             }
             j++;
           }
           bool = true;
           j = 0;
           if (zeroCount == 1){
                count++;
            }
            zeroCount=0;
            i++;
   }
       System.out.println(count);
   }

ما رأيكم بهذا ؟

def subin(dec) :
    zeros = 0

    while dec > 0:
        if zeros == 2:
            return False

        if dec % 2 == 0:
            zeros += 1

        dec //= 2

    return zeros == 1;

s = 0
for i in range(1, 10):
    if subin(i):
        s += 1
print('sum:', s)

output

sum: 3

لا أعلم، هل المسألة مكتوبة خطأً، ولكن هناك من حل المسألة. أو أني لم أفهم المسألة، فقد حاولت فهم هذه الجملة قدر المستطاع ولم أفهم:

اريد عدد الارقام التي بينهما (معهما) التي تحوي في تمثيلها الثنائي (الباينري) صفراً واحداً

حاولت أن أفهم من أحد الحلول التي قدمها بعض المشاركين، فأجدها إما بلغة بايثون، أو جافا سكربت (والتي لا أعرف كيف ينفذ برنامجها).

أقرأ مثالك الأول، فأظن أن الحل هو معرفة عدد الخانات المختلفة بين العددين (في الصيغة الثنائية)، ولكن المثال الثاني ينسف ذلك تمامًا. وأما الأخير فهو لا يوضح شيئًا البتة (لمن لم يفهم المثالين السابقين)!

لغة روبي , xmax المدخل الاكبر , xmin المدخل الاصغر

سرعة .. O(log2(m)) بحيث m المدخل الاكبر

اداء الذاكرة O(1)

إن شاء الله يكون الحل صحيح

xmax = 6
xmin = 5

startRange = Math.log2(xmin).ceil
endRange = Math.log2(xmax).ceil

biggestNumber = (2**endRange)-1
smallestNumber = (2**startRange)-1

count  = 0
powerNumber = 1

for i in 0...(endRange-1)
    bnumber = biggestNumber-powerNumber
    snumber = smallestNumber-powerNumber


    if ((bnumber <= xmax and bnumber >= xmin) or 
         (snumber <= xmax and snumber >= xmin))
        count += 1
    end
    powerNumber = powerNumber * 2
end


puts "Result: #{count}"