حل سوالی از مسابقه ACM بوعلی سینا
acm
Problem: arranging digits
Input File : Standard Input
Output : Standard Output
Given a number, we can form a number chain by
۱. arranging its digits in descending order
۲. arranging its digits in ascending order
۳. subtracting the number obtained in (2) from the number obtained (1) to form a new number
۴. and repeat these steps unless the new number has already appeared in the chain
Note that 0 is a permitted digit. The number of distinct numbers in the chain is the length of the chain. You are to write a program that reads numbers and outputs the number chain and the length of that chain for each number read.
Input
The input consists of a sequence of positive numbers, all less than 10^50 , each on its own line, terminated by 0. The input file contains at most 5000 numbers.
Output
The output consists of the number chains generated by the input numbers, followed by their lengths exactly in the format indicated below. After each number chain and chain length, including the last one, there should be a blank line. No chain will contain more than 1000 distinct numbers.
Sample Input
۱۲۳۴۵۶۷۸۹
۱۲۳۴
۴۴۴
۰
Sample Output
Original number was 123456789
۹۸۷۶۵۴۳۲۱ – ۱۲۳۴۵۶۷۸۹ = ۸۶۴۱۹۷۵۳۲
۹۸۷۶۵۴۳۲۱ – ۱۲۳۴۵۶۷۸۹ = ۸۶۴۱۹۷۵۳۲
Chain length 2
Original number was 1234
۴۳۲۱ – ۱۲۳۴ = ۳۰۸۷
۸۷۳۰ – ۰۳۷۸ = ۸۳۵۲
۸۵۳۲ – ۲۳۵۸ = ۶۱۷۴
۷۶۴۱ – ۱۴۶۷ = ۶۱۷۴
Chain length 4
Original number was 444
۴۴۴ – ۴۴۴ = ۰
۰ – ۰ = ۰
Chain length 2
ترجمه این سوال در حالت کلی این می شود :یک عدد از کاربر می گیریم که حداکثر ۵۰ رقم است .عدد را یک بار صعودی می کند و یک بار آن را نزولی می کند و عدد بزرگ را همانی که به صورت نزولی نوشته شده است را منهای عدد کوچک تر می کند بعد عدد جدیدی به دست می آید که باز هم همین کار را با آن می کنیم آنقدر این کار را می کنیم تا دو عدد حاصل از منها کردن در دو مرحله متوالی با هم برابر شوند این کار را می کنیم تا ۱۰۰۰ بار اگر شد تعداد مراحلی را که انجام داده ایم مینویسیم اگر نه که هیچ.
تابع تفریق اعداد بزرگ
تنها نکته این برنامه نوشتن تابعی برای تفریق کردن ۲ عدد ۵۰ رقمی است. در این جا برای راحتی کار از رشته ای کاراکتری استفاده می کنیم آن هم به طول ۵۰ کاراکتر .تابع sub کار تفریق ۵۰ کاراکتر را انجام می دهد.تابع dec_arr به صورت نزولی عدد را می نویسد. تابع asc_arr عدد را به صورت صعودی می نویسد. تابع compare به دو عدد مقایسه انجام می دهد.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 | #include <stdio.h> #include <conio.h> #include <ctype.h> #include <string.h> void sub(char x[50],char y[50],char z[50]) { int i,j,temp=0; for(i=49;i>=0;i--) { temp=x[i]-y[i]; if(temp>=0) { z[i]=temp+48; } else { j=i-1; while(x[j]=='0') { x[j]='9'; j--; } x[j]=x[j]-1; z[i]=((x[i]-48)-(y[i]-48)+10)+48; } } } //************************************************** void dec_arr(char a[50],char b[50]) { int i,j,p; char temp; p=-1; while(a[++p]=='0') for(i=0;i<50;i++) b[i]=a[i]; for(i=p;i<50;i++) for(j=p;j<=i;j++) if(b[i]>b[j]) { temp=b[i]; b[i]=b[j]; b[j]=temp; } } //************************************************** void asc_arr(char a[50],char b[50]) { int i,j; char temp; for(i=0;i<50;i++) b[i]=a[i]; for(i=0;i<50;i++) for(j=0;j<=i;j++) if(b[i]<b[j]) { temp=b[i]; b[i]=b[j]; b[j]=temp; } } //*********************************************** int compare(char x[50],char y[50]) { int i; for(i=0;i<50;i++) { if(x[i]>y[i]) return 1; if(x[i]<y[i]) return -1; } return 0; } //*********************************************** int main(void) { char x[50],y[50],temp[50],z[50],a[50],b[50]; int i,len1; for(i=0;i<50;i++) { z[i]=x[i]=y[i]=temp[i]=a[50]=b[50]='0'; } printf("Enter the first number:"); gets(temp); len1=strlen(temp); for(i=0;i<len1;i++) x[50-len1+i]=temp[i]; for(i=0;i<50;i++) z[i]=x[i]; int counter=0; do { for(i=0;i<50;i++) x[i]=z[i]; asc_arr(x,a); dec_arr(x,b); int k; sub(b,a,z); counter++; if(counter>=1000) { printf("there is no end for this number"); return 0; } } while(compare(x,z)); printf("chain lenght = %d",counter); return 0; } |
بابا امام زمان ظهور کرد , هنوز پروژه ی شما ارائه نشد! (:
بیشتر پروژه را آقای یگانگی طرح کردن ،هنوز به من همم نداده!
ع
بیشتر پروژه را آقای یگانگی طرح کردن ،هنوز به من همم نداده!
سلام آقای دلیرانی قرار بود موضوع پروژه رو بزارید روی سایت پس کو؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟
تا روز شنبه حتما می گذارم.
شاید این شنبه بیاید شاید :))))
perhaps