例43 Excel地址
問題描述
Excel是常用的辦公軟體，在Excel表格中，每個單元格都有唯一的地址表示，比如：第12行第4串列示為“D12”，第5行第255串列示為“IU5”，
事實上，Excel提供了兩種地址表示方法，還有一種表示法叫做RC格式地址， 第12行第4串列示為“R12C4”，第5行第255串列示為“R5C255”，
撰寫程式，實作從RC地址格式到常規地址格式的轉換，
輸入格式
第1行是一個正整數n（n<100），表示接下來有n行輸入資料，
接著輸入的n行資料是RC格式的Excel單元格地址表示法，
輸出格式
輸出n行資料，每行是轉換后的常規地址表示法，
輸入樣例
2
R12C4
R5C255
輸出樣例
D12
IU5
（1）編程思路，
首先將輸入的RC格式地址中的行和列的值求出來，例如，輸入R5C255后，可求出行值row=5，列值col=255，
之后將列值col轉換成26進制表示的數，方法為將col不斷除以26，記下余數，直到商為0，每個余數保存到陣列d中，例如，255轉換為26進制數是一個兩位數，高位為9（保存到d[1]中），低位為21（保存到d[0]）中，然后將數字映射為字母，1對應A，2對應B，…，9對應I，…，21對應U，…，26對應Z，這樣，255串列示為IU，
但在具體處理時，由于1~26表示A~Z，因此得到的余數若為0，則應對應為26，即26不進位，由此需向前借1位，例如，列值col=52時，轉換為26進制數碼d[1]=2,d[0]=0，此時由于d[0]<=0，d[0]=d[0]+26=26，d[1]=d[1]-1=1，再對應表示為AZ，
（2）源程式，
#include <stdio.h>
#include <string.h>
int main()
{
int n;
scanf("%d",&n);
while (n--)
{
char str[24],colstr[9];
int row,col,d[7],i,k,len,flag;
scanf("%s",str);
row=0; col=0; flag=0;
for (i=1;str[i]!='\0';i++)
{
if (str[i]!='C')
{
if (flag==0)
row=row*10+str[i]-'0';
else
col=col*10+str[i]-'0';
}
else
flag=1;
}
len=0;
while (col!=0)
{
d[len++]=col%26;
col/=26;
}
for (i=0;i<len-1;i++)
if (d[i]<=0)
{
d[i]=d[i]+26;
d[i+1]--;
}
if (d[len-1]==0) len--;
k=0;
for (i=len-1;i>=0;i--)
colstr[k++]=d[i]-1+'A';
colstr[k]='\0';
printf("%s%d\n",colstr,row);
}
return 0;
}
習題43
43-1 Hexadecimal Numbers
本題選自POJ題庫 （http://poj.org/problem?id=1715）
Description
The base of the hexadecimal system is 16. In order to write down numbers in this system one uses 16 digits 0,1,...,9,A,B,C,D,E,F. The capital letters A,..,F stands for 10,..,15, respectively. For instance the value of the hexadecimal number CF2 is 12 * 162 + 15 * 16 + 2 = 3314 in the decimal system. Let X be the set of all positive integers whose hexadecimal representations have at most 8 digits and do not contain repetitions of any digit. The most significant digit in such a representation is not zero. The largest element in X is the number with the hexadecimal representation FEDCBA98, the second largest is the number FEDCBA97, the third is FEDCBA96 and so forth.
Write a program that: finds the n-th largest element of X;
Input
The first line of the file standard input contains integer n in the decimal representation. n does not exceed the number of elements of X.
Output
Your program should output the n-th largest element in X in the hexadecimal representation.
Sample Input
11
Sample Output
FEDCBA87
（1）編程思路，
本題是給定16進制數的16個數碼，求第k大的數，要求數的長度最大為8，并且每個數碼互不相同，
第1大的數為FEDCBA98，第2大的數為FEDCBA97，第2大的數為FEDCBA96，…，倒數第2大的數為1，最小的數為0，
先確定第k大的數的位數，最多為8位，8位數一共有15*15*14*13*12*11*10*9=486486000個，最高位不能為0，在1~F這15個數碼中任取一個作為最高位，第2位在剩下的15個數碼中任取1位，第3位在剩下的14個數碼中任取1位，…，第8位在剩下的9個數碼中任取1位，所以8位數的個數為486486000個，同理，7位數的個數為15*15*14*13*12*11*10=54054000個；6位數的個數為15*15*14*13*12*11=5405400個；5位數的個數為15*15*14*13*12=491400個；4位數的個數為15*15*14*13=40950個；3位數的個數為15*15*14=3150個；2位數的個數為15*15=225個；1位數的個數為15個（指非0，若包括0，則有16個），上述所有數加起來為546481140，即第546481141大的數為0，
定義陣列int m[10]={0,15,225,3150,40950,491400,5405400,54054000,486486000};保存各長度數的個數，由上面分析知，第486486000大的數是最小的8位數10234567，第486486001大的數應該就是最大的7位數FEDCBA9；第486486000+54054000=540540000大的數一定是最小的7位數1023456，第540540001大的數一定是最大的6位數FEDCBA，由此可以確定第k大的數的位數，若k<=486486000，則位數為8，同時可確定也是第k大的8位數；若486486000<k<=486486000+54054000，則位數為7，同時可確定其是第k-486486000的7位數；…，以此類推，
確定第k大的數也是第n大的len位數后，再從高位往低位進行處理，若最高位確定為F，則后7位一共有15*14*13*12*11*10*9，簡記為mul(15,7)，表示從15~9這連續的7個數相乘，也就是說，若k<=mul(15,7)，則第k大的8位數最高位一定為F，可以驗證第mul(15,7)=32432400大的數一定為F0123456，則第32432401大的數一定為EFDCBA98，若mul(15,7)<k<=2*mul(15,7)，則最高位一定為E，若2*mul(15,7)<k<=3*mul(15,7)，則最高位一定為D，…，即最高位為k/mul(15,7)對應16個數碼的映射，映射為0—F，1—E，2—D，15—0，
確定了最高位后，再確定次高位，此時，需要將k%mul(15,7)，不妨設結果為k1，若確定次高位是剩下的15個數碼中的最大，則后面6位一共可表示14*13*12*11*10*9=2162160，簡記為mul(14,6)，也就是說若k1<=mul(14,6)，則第k大的數的次高位一定是剩下15個數碼中最大的，若mul(14,6)<k1<=2*mul(14,6)，則第k大的數的次高位一定是剩下15個數碼中第2大的，若2*mul(14,6)<k1<=3*mul(14,6)，則第k大的數的次高位一定是剩下15個數碼中第3大的，…，即次高位為k1/mul(14,6)對應剩下15個數碼的映射，可以驗證第34594560（即32432400+2162160）大的數一定為EF012345，第34594561大的數一定為EDFCBA98，這是由于k大于mul(15,7)，所以k的最高位為E，k1=k%mul(15,7)=2162161，k1>mul(14,6)，所以次高位是除去E后第2大的數碼，所以為D，
同理，可確定之后的各位，
（2）源程式，
#include <stdio.h>
int mul(int x,int y)
{
int p=1;
while (y--)
{
p*=x;
x--;
}
return p;
}
int main()
{
int m[10]={0,15,225,3150,40950,491400,5405400,54054000,486486000};
char num[17]="0123456789ABCDEF";
int b[10],vis[20];
int n;
while (scanf("%d",&n)!=EOF)
{
if (n>=546481141)
{
printf("0\n");
continue;
}
int len=8;
while (n>m[len])
{
n-=m[len]; len--;
}
n--;
int i,j;
for (i=len;i>=1;i--)
{
int t=mul(15+i-len,i-1);
b[i]=n/t;
n%=t;
}
for (i=1;i<=16;i++)
vis[i]=0;
for (i=len;i>=1;i--)
{
int s=0;
for (j=1;j<=16;j++)
{
if (vis[j]==0)
{
s++;
if (s==b[i]+1)
{
vis[j]=1;
break;
}
}
}
printf("%c",num[16-j]);
}
printf("\n");
}
return 0;
}
43-2 識別碼
問題描述
某系統中給每件物品編制一個唯一的識別碼，該識別碼由26個小寫字母中最多50個字符組成，任何給定代碼的字符集均可隨意選擇，但一旦選擇了一組字母，在更改該組字母之前，將使用從該組字母派生的所有可能代碼作為識別碼，
例如，假設選定的字符集包含3個“a”、2個“b”和1個“c”，那么由這組字母編制的識別碼按字母順序依次如下：
aaabbc
aaabcb
……
abaabc
abaacb
ababac
……
cbbaaa
撰寫一個程式來幫助發布這些識別碼，輸入一個不超過50個小寫字母（可能包含重復字符）組成的字串，輸出其下一個排列字串，
輸入
輸入由一系列行組成，每行包含一個表示給定代碼的字串，整個檔案將以一行結尾，該行由一個#組成，
輸出
求輸入字串的下一個排列串，若不存在，就輸出No Successor，
輸入樣例
abaacb
cbbaa
#
輸出樣例
ababac
No Successor
（1）編程思路，
求輸入字串的下一個排列字串的方法如下，為描述方便，設字串中字符記為1~n，
設P是1～n的一個全排列：p=p1p2……pn
=p1p2……pj-1pjpj+1……pk-1pkpk+1……pn
1）從排列的右端開始，找出第一個比右邊數字小的數字的序號j（j從左端開始計算），即 j=max { i | pi < pi+ 1}，
2）在pj的右邊的數字中，找出全部比pj大的數中最小的數字pk，即 k=max{i|pi>pj}，由于右邊的數從右至左是遞增的，因此k是全部大于pj的數字中序號最大者，
3）交換pj，pk，
4）再將pj+1……pk-1pkpk+1……pn倒轉得到排列
p’=p1p2…..pj-1pjpn…..pk+1pkpk-1…..pj+1，
這就是排列p的下一個排列，
例如，設有排列：1，3，5，4，2，其中5-4-2即為遞增序列，找到a[1]=3；從上述序列中找一個比a[1]（3）大的最小數（4），并將且交換這兩個數，于是1，3，5，4，2變換為1，4，5，3，2，再將4后面的數字遞增排列，即1，4，2，3，5，
因此，得到1，3，5，4，2的下一個排列為1，4，2，3，5，
（2）源程式1，
#include <stdio.h>
#include <string.h>
int theNext(char a[],int n)
{
int len =n-1,front;
int flag=0;
while (len>0)
{
if(a[len-1]<a[len])
{
front = len-1;
flag=1;
break;
}
len--;
}
if (! flag)
return 0;
len =n-1;
int min=200;
while (len>front)
{
if(a[len]>a[front])
{
min=len;
break;
}
len--;
}
char temp=a[min];
a[min]=a[front];
a[front]=temp;
int i,j;
for(i=front+1;i<n;i++)
{
for(j=i;j<n;j++)
{
if(a[i]>a[j])
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
}
return 1;
}
int main()
{
char str[51];
while (scanf("%s", str)&& str[0]!='#')
{
if(theNext(str, strlen(str)))
printf("%s\n", str);
else
printf("No Successor\n");
}
return 0;
}
（3）源程式2，
也可以用庫函式next_permutation直接求某個排列的下一個排列，撰寫的源程式如下，
#include <stdio.h>
#include <algorithm>
using namespace std;
int main()
{
char str[51];
while (scanf("%s", str)&& str[0]!='#')
{
if(next_permutation(str, str + strlen(str)))
printf("%s\n", str);
else
printf("No Successor\n");
}
return 0;
}
43-3 排列順序
問題描述
1~n這n（2 <= n <= 8,000）個數排成一行，給出從第2個數到最后一個數每個數之前比它小的數的個數，求出這n個數的排列順序，
輸入
輸入包括兩行，第1行為整數n；第2行有n-1個整數a1，a2，…，ai，…，an-1，其中ai為第I+1個數之前的i個數比第i+1個數小的數的個數，
輸出
輸出n個數的排列順序，每個數占1行，
輸入樣例
5
1 2 1 0
輸出樣例
2
4
5
3
1
（1）編程思路，
我們先來看看樣例是如何確定的，有1~n這5個數，從第2個數到最后一個數每個數之前比它小的數的個數分別為1 2 1 0，從最后一個數往前依次確定每個數，最后一個數之前比它小的數為0，顯然最后一個數只能填最小的數1，否則，它前面至少有1個1比它小；倒數第2個數之前比它小的數有1個，1已填過，若倒數第2個數填 2，則前面的數都比它大，不滿足，因此考慮填 3，此時前面只有1個2比它小，滿足要求；倒數第3個數之前比它小的數為2，1和3已填過，若填寫2或4，則前面比它小的數或為0或為1，達不到2，因此只能填寫5，前面存在2和4比它小；倒數第4個數之前比它小的數為1，1已填過，填寫2不符合要求，3已填過，填寫4，之前存在2比它小，正好滿足要求；剩下的一個未填寫的數字2，正好填在第1位，由此，得到填寫序列為2，4，5，3，1，
用回圈模擬上面給出的填數程序，從后往前依次確定序列中的第n到第2個數應該填寫1~n中哪一個數，定義陣列int vis[8001];保存每個數是否填寫過，若數i已填寫，則置vis[i]=1，對于每個位置p應填寫的數，從1~n中統計vis[i]==0的數的個數cnt，若統計到k時，cnt正好等于a[p]+1，即比k小的數有a[p]個，則p位置就填寫k，同時置vis[k]=1，
之后，將1~n中僅有的vis[i]==0的數填在序列的第1個位置，
（2）源程式，
#include <stdio.h>
#include <string.h>
#define maxn 8001
int vis[maxn];
int a[maxn], ans[maxn];
int main(void)
{
int n,i,k,t,cnt;
scanf("%d",&n);
memset(vis, 0, sizeof(vis));
for (i=1; i<n; i++)
scanf("%d", &a[i]);
t = n;
for (i=n-1; i>=1; i--) // 從后往前依次確定序列中的第n到第2個數
{
cnt=-1, k=1;
for (k=1; k<=n; k++)
{
if (!vis[k]) cnt++; // 統計未確定位置的數中有多少個比k小
if (cnt == a[i])
{
vis[k] = 1; // 標記數k已確定位置
break;
}
}
ans[t--] = k;
}
for (i = 1; i <= n; i++) // 確定原序列中的第1個數
if (! vis[i])
{
ans[t] = i;
break;
}
for (i = 1; i <= n; i++)
printf("%d\n",ans[i]);
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/412834.html
標籤：C
上一篇：C++ 從&到&&
下一篇：組態檔動態重繪