注册 登录
编程论坛 C++教室

[求助]请大家帮我看看这个程序

青格儿 发布于 2007-09-05 15:27, 1281 次点击
我这有个 测试是不是逆序数的程序,可是我有的地方看不懂,请大家帮我分析下,我先这在谢谢了!

在线性代数里有这么一个概念:有一个数列,如21543,
1的前面有1个数比它要大,4的前面有1个数比它大,
3的前面有2个数比它大,总数是1+1+2=4
所以21543的逆序数就是4

#include <cstdio>

int main()
{
while(!scanf("%*d\n"))
{
// int c, i;
int s = 0, t, buf[256 * 2] = {0};
int *mipmap[] = {buf + 2, buf + 4, buf + 8, buf + 16, buf + 32, buf + 64, buf + 128, buf + 256};//这为什么这么定义?
while((t = getchar()) != '\n')
{
mipmap[7][t]++, t & 1 || (s += mipmap[7][t + 1]), t >>= 1;//这是什么意思?
mipmap[6][t]++, t & 1 || (s += mipmap[6][t + 1]), t >>= 1;
mipmap[5][t]++, t & 1 || (s += mipmap[5][t + 1]), t >>= 1;
mipmap[4][t]++, t & 1 || (s += mipmap[4][t + 1]), t >>= 1;
mipmap[3][t]++, t & 1 || (s += mipmap[3][t + 1]), t >>= 1;
mipmap[2][t]++, t & 1 || (s += mipmap[2][t + 1]), t >>= 1;
mipmap[1][t]++, t & 1 || (s += mipmap[1][t + 1]), t >>= 1;
mipmap[0][t]++, t & 1 || (s += mipmap[0][t + 1]);
/*
for (t = c, i = 0; i < 8; i++, t >>= 1)
{
mipmap[7 - i][t]++;
if (0 == (t & 1))
s += mipmap[7 - i][t + 1];
}
*/
}
printf("%d\n", s);
}
return 0;
}
16 回复
#2
福尔摩斯2007-09-05 15:59
要是我,我绝对不这样写

直接2个for循环体就解决问题了
#3
wsy2007-09-05 20:25
我连1楼的都不会写 呵呵 2楼的大侠能 否百忙中抽出点时间写出 那两个FOR 循环 让我能学一下
#4
puying20082007-09-05 22:08
#include<iostream.h>
void main()
{
static int count=0;
int a[5]={2,1,5,4,3};
for(int i=1;i<5;i++)
for(int j=0;j<i;j++)
{
if(a[j]>a[i]) count++;
}
cout<<count<<endl;
}
#5
puying20082007-09-05 22:18

应该是这样才对:
#include<iostream.h>
void main()
{
static int count=0;
int n;
cout<<"Input the number of the array:"<<endl;
cin>>n;
int *p=new int[n];
cout<<"Intput the elments"<<endl;
for(int k=0;k<n;k++)
cin>>*p;

for(int i=1;i<n;i++)
for(int j=0;j<i;j++)
{
if(p[j]>p[i]) count++;
}
delete [] p;
cout<<count<<endl;
}

#6
青格儿2007-09-06 09:29
楼上的不对,请看清要求!

就你上面那组:21543

当i=3时,j 不是从0再开始比较!

请大家帮我看看那两句什么意思?从家这个程序时间复杂度小啊!还有编译程序时出现这个提示:
nixu.cpp:35:2:warning :no newline at end of file

就像1楼那个程序也会出现这个!怎么办,才能不出现这个?
#7
青格儿2007-09-06 09:45
/*
for (t = c, i = 0; i < 8; i++, t >>= 1)
{
mipmap[7 - i][t]++;
if (0 == (t & 1))
s += mipmap[7 - i][t + 1];
}
*/

这段是它的注释, 可是我还是看着迷惑!请各位朋友帮帮我,谢谢!
#8
virusswb2007-09-06 14:41
下面给个思路吧

int num=0;
for(int i=1;i<len(input);i++)
{
for(int j=0;j<i;j++)
{
if(input[j]>input[i])
num++;
}
}
#9
aipb20072007-09-06 20:44
很明显,用两个for是不考虑效率的做法!
#10
福尔摩斯2007-09-06 21:41
以下是引用aipb2007在2007-9-6 20:44:48的发言:
很明显,用两个for是不考虑效率的做法!

你有什么更好的算法?

#11
aipb20072007-09-06 22:45
以下是引用福尔摩斯在2007-9-6 21:41:37的发言:

你有什么更好的算法?

比较排序里最好的效率是O(nlgn),比如归并排序改下就行。

#12
gylin_19822007-09-07 16:15
#include <iostream>
#include <string>
using namespace std;
int main()
{
char str[20];
int len=0;
int count=0;
while(gets(str))
{
len = strlen(str);
for(int i=1; i<len; i++)
for(int j=0; j<i; j++)
{
if( str[j] > str[i])
count++;
}
cout<<"count="<<count<<endl;
count = 0;
}
return 0;
}
#13
青格儿2007-09-07 20:59
int *mipmap[] = {buf + 2, buf + 4, buf + 8, buf + 16, buf + 32, buf + 64, buf + 128, buf + 256};这为什么这么定义?
while((t = getchar()) != '\n')
{
mipmap[7][t]++, t & 1 || (s += mipmap[7][t + 1]), t >>= 1;//这是什么意思?


请大家帮我看看这两句!回答这两句后面的问题啊!移位运算....?

[此贴子已经被作者于2007-9-7 21:03:08编辑过]

#14
sunkaidong2007-09-11 10:26
楼上有什么好的方法啊,而且能不能把程序的意思说说呢?
#15
青格儿2007-09-12 09:49
1楼的程序就是好方法啊!还有注释!

自己再顶下,希望有人给我解释下,也就是说我也不懂这个程序的算法,谁可以帮我求出它的时间复杂度,还有帮我注释下它的意思,谢谢!
int *mipmap[] = {buf + 2, buf + 4, buf + 8, buf + 16, buf + 32, buf + 64, buf + 128, buf + 256};这为什么这么定义?
while((t = getchar()) != '\n')
{
mipmap[7][t]++, t & 1 || (s += mipmap[7][t + 1]), t >>= 1;这是什么意思?

[此贴子已经被作者于2007-9-12 9:50:20编辑过]

#16
青格儿2007-09-19 10:49
为什么没人帮我?这个问题太简单了,不值得回复下吗?
#17
caierfeng2007-09-19 16:16
不用俩个for的实在想不出来....求序列里每个数前面大于该数的个数累加等价于求每个数后面小于该数个数累加
只有本站会员才能查看附件,请 登录

1